当前位置：首页 > news >正文

LintCode第1712题 - 和相同的二元子数组

news 来源：原创 2025/8/4 8:36:41

描述

在由若干 0 和 1 组成的数组 A 中，有多少个和为 S 的非空子数组

样例 1:

输入：A = [1,0,1,0,1], S = 2
输出：4
解释：
如下面黑体所示，有 4 个满足题目要求的子数组：
[1,0,1]
[1,0,1]
[1,0,1,0]
[0,1,0,1]

样例 2:

输入：A = [0,0,0,0,0,0,1,0,0,0], S = 0
输出：27
解释：
和为 S 的子数组有 27 个

思路1 采用同向双指针法通过暴力双指针枚举所有起点 + 滑动右指针

每轮固定左指针 left，右指针从 left 向右滑动；每次累加和，如果等于 S，就记录这个子数组；关键点是从每个 left 出发，向右滑，不能随便跳过任何一个组合

代码1:

public class Solution {

public int numSubarraysWithSum(int[] A, int S) {

int n=A.length;

int count=0;

for(int left = 0; left < n; left++)//同向双指针法计算是否为目前值S

{

int accumulatedNum = 0;

for (int right = left; right < n; right++) {

accumulatedNum += A[right];

if (accumulatedNum == S) {

count++;

} else if (accumulatedNum > S) {

break; // 再滑动右指针没意义了

}

return count;

}

思路2 前缀和 + 哈希表

任意一个子数组 [i..j] 的和 = prefixSum[j] - prefixSum[i-1] 若要求 sum[i..j] = S，则等价于： prefixSum[j] - prefixSum[i-1] == S → prefixSum[i-1] == prefixSum[j] - S

prefixMap 来记录前缀和出现的次数，作用是：

键（Key）	值（Value）
某个前缀和 `x`	这个前缀和 `x` 出现过多少次

prefixMap.put(0, 1);

前缀和为 0 出现了 1 次（这是初始化）

它允许我们从下标 0 开始的子数组也能被统计进来

accumulatedNum 当前前缀和，也就是从 A[0] 到 A[i] 的累加值

count 当前找到的子数组个数，最终返回这个值

步骤 1：累加前缀和

accumulatedNum += A[i]; // 累加前缀和将当前元素 A[i] 累加到 accumulatedNum 中； accumulatedNum 代表前缀和 prefixSum[i]

每次比较都是当前前缀和-s 当有

既等式

prefixSum[j] - prefixSum[i-1] == S
→ prefixSum[i-1] == prefixSum[j] - S
→ accumulatedNum - S

是我们想找的值意思为在前面的位置出现过这样一个前缀和，
这样从那个位置之后到我当前位置，就刚好是一个和为 S 的子数组

prefixMap.get(accumulatedNum - S)之前有多少个位置，它们的前缀和等于 accumulatedNum - S

每一个都可以作为「合法子数组的起点」，从那个点到当前 i 的子数组和为 S。
所以：prefixMap.get(accumulatedNum - S) 就是当前命中的合法子数组个数

prefixMap.put(accumulatedNum, prefixMap.getOrDefault(accumulatedNum, 0) + 1);
把当前的前缀和 accumulatedNum 的出现次数 +1

因为我们要统计「从前面某个位置 i 到当前位置 j 的和为 S 的子数组数量」。

每一个前缀和，都可能为后面提供组合，所以我们必须记录它出现的次数

import java.util.*;

public class Solution {
public int numSubarraysWithSum(int[] A, int S) {
int accumulatedNum = 0; // 当前的前缀和
int count = 0;

Map<Integer, Integer> prefixMap = new HashMap<>();
prefixMap.put(0, 1); // 初始化：前缀和为 0 出现了 1 次

for (int i = 0; i < A.length; i++) {
accumulatedNum += A[i]; // 累加当前前缀和

// 如果之前出现过 accumulatedNum - S，就说明找到了满足条件的子数组
if (prefixMap.containsKey(accumulatedNum - S)) {
count += prefixMap.get(accumulatedNum - S);
}

// 更新当前前缀和出现次数
prefixMap.put(accumulatedNum, prefixMap.getOrDefault(accumulatedNum, 0) + 1);
}

return count;
}
}

一个疑问点是如果不写

那么就会漏掉那些从 index = 0 开始就满足和为 S 的子数组

例 A = [1, 0, 1], S = 2

有 prefixMap.put(0, 1) 的时候：

i	A[i]	accumulatedNum	accumulatedNum - S	prefixMap命中	count
0	1	1	-1	❌	0
1	0	1	-1	❌	0
2	1	2	0	✅	1

最终结果：找到了子数组 [0, 1, 2]，和为 2。

当prefixMap.put(0, 1)没有的时候

当前累计为 2 的时候，你想找的前缀和是 0，但 prefixMap 里没有

prefixMap.getOrDefault(accumulatedNum, 0) 会取下标为0的值因为没有放入1 则

这段合法子数组 [1, 0, 1] 就不会被统计即错误结果最终结果是:count=0

推荐刚开始学习使用双指针法进阶使用前缀和 + 哈希表

LintCode第1712题 - 和相同的二元子数组

描述在由若干 0 和 1 组成的数组 A 中，有多少个和为 S 的非空子数组样例 1: 输入：A [1,0,1,0,1], S 2 输出：4 解释： 如下面黑体所示，有 4 个满足题目要求的子数组： [1,0,1] [1,0,1] [1,0,1,0] [0,1,…...

编程日记 2025/8/4 8:36:41

网络HTTPS协议

Https HTTPS（Hypertext Transfer Protocol Secure）是 HTTP 协议的加密版本，它使用 SSL/TLS 协议来加密客户端和服务器之间的通信。具体来说： • 加密通信：在用户请求访问一个 HTTPS 网站时，客户端&#x…...

编程日记 2025/8/4 10:20:40

0322-数据库、前后端

前端 <!DOCTYPE html> <html> <head> <meta charset"UTF-8"> <title>Insert title here</title> <script srcjs/jquery-3.7.1.min.js></script> <script> //jquaryajax发起请求 //传参形式不同 post用data{}…...

编程日记 2025/8/4 1:23:14

六十天前端强化训练之第二十六天之Vue Router 动态路由参数大师级详解

欢迎来到编程星辰海的博客讲解看完可以给一个免费的三连吗，谢谢大佬！ 目录一、知识讲解 1. Vue Router 核心概念 2. 动态路由参数原理 3. 参数传递方案对比二、核心代码示例 1. 完整路由配置 2. 参数接收组件 3. 导航操作示例三、实现效果示…...

编程日记 2025/8/4 10:15:44

一、拓朴图二、实验配置 1.基础配置 1.1接口IP及服务配置 [PPPoE Client]interface GigabitEthernet 0/0/0 [PPPoE Client-GigabitEthernet0/0/0]service-manage all permit [NAS]interface GigabitEthernet 0/0/0 [NAS-GigabitEthernet0/0/0]ip add 192.168.0.2 24 [NAS-Gi…...

编程日记 2025/8/4 10:14:00

uni-app——数据缓存API

数据缓存API 在 uni-app 开发中，数据缓存 API 起着重要作用，它能够将需要的数据保存到本地，同时也提供了获取本地缓存数据、移除缓存数据以及清理缓存数据的功能。在实际项目里，数据缓存 API 常被用于存储会员登录状态信息、购物…...

编程日记 2025/8/3 18:24:02

不做颠覆者，甘为连接器，在技术叠层中培育智能新物种

--- 一、技术融合的必然：从“非此即彼”到“兼容共生” 当大模型的热浪撞上传统IT的礁石，企业智能化的真相浮出水面： 新旧技术的“量子纠缠”：MySQL与向量数据库共享数据总线，规则引擎与大模型共处决策链路需求进…...

编程日记 2025/8/3 13:11:18

尝试在软考65天前开始成为软件设计师-计算机网络

OSI/RM 七层模型层次名功能主要协议7应用层实现具体应用功能 FTP(文件传输)、HTTP、Telnet、 POP3(邮件)SMTP(邮件) ------- DHCP、TFTP(小文件)、 SNMP、 DNS(域名) 6表示层数据格式,加密,压缩.....5会话层建立,管理&终止对话4传输层端到端连接TCP,UDP3网络层分组传输&a…...

编程日记 2025/8/4 10:15:43

JDBC 连接字连接 KingbaseES支持主从负载均衡参数说明。

JDBC 连接字符串是用于连接 KingbaseES（人大金仓数据库）的，支持主从负载均衡。让我们逐一解析各个参数的作用，并探讨如何调整到最优。参数解析 jdbc:kingbase8://10.10.14.19:54321/xxx_onlinejdbc:kingbase8://：指定…...

编程日记 2025/8/4 10:20:40

OpenCV旋转估计（4）生成一个字符串表示的匹配图函数 matchesGraphAsString()

操作系统：ubuntu22.04 OpenCV版本：OpenCV4.9 IDE:Visual Studio Code 编程语言：C11 算法描述 matchesGraphAsString 函数是OpenCV库中的一部分，位于 cv::detail 命名空间下。这个函数的主要作用是生成一个字符串表示的匹配图&am…...

编程日记 2025/8/3 14:45:46

扣子平台知识库不能上传成功

扣子平台知识库不能上传成功目录扣子平台知识库不能上传成功查看模板复制头部到自己的excel中json数据转为excel或者csv（一定使用excel，csv总是报错） 查看模板复制头部到自己的excel中 json数据转为excel或者csv（一定使用excel&…...

编程日记 2025/8/4 10:19:14

CIFAR10 数据集自定义处理方法

CIFAR10 数据集自定义处理方法可以自定义训练集和测试集中不同类别的样本的数量。可用于模拟类别不平衡问题，存在混淆数据问题。 import torch import torchvision.datasets as dsets import torchvision.transforms as transforms from torch.utils.data import…...

编程日记 2025/8/4 10:19:28

当发现提示少文件，少目录时时，external.css的内容

[ERROR ]17:30:44| Loger: 处理群消息时发生错误：[Errno 2] No such file or directory: \\venv\\lib\\site-packages\\ncatbot\\utils\\template/external.css venv\\lib\\site-packages\\ncatbot\\utils\\template/external.css ["https://stackpath.boots…...

编程日记 2025/8/4 5:34:23

OpenHarmony 开源鸿蒙北向开发——linux使用make交叉编译第三方库

这几天搞鸿蒙，需要编译一些第三方库到鸿蒙系统使用。头疼死了，搞了一个多星期总算搞定了。开贴记坑。一、SDK下载 1.下载在linux下使用命令 wget https://cidownload.openharmony.cn/version/Master_Version/OpenHarmony_5.1.0.54/20250313_02…...

编程日记 2025/7/30 17:54:02

【计算机网络】网络简介

文章目录 1. 局域网与广域网1.1 局域网1.2 广域网 2. 路由器和交换机3. 五元组3.1 IP和端口3.2 协议3.3 协议分层 4. OSI七层网络协议5. TCP/IP五层模型5.1 TCP/IP模型介绍5.2 网络设备所在分层 6. 封装与分用6.1 数据包的称谓6.2 封装6.3 分用 1. 局域网与广域网 1.1 局域网 …...

编程日记 2025/8/4 10:19:29

k8s--集群内的pod调用集群外的服务

关于如何让同一个局域网内的Kubernetes服务的Pod访问同一局域网中的电脑上的服务。可能的解决方案包括使用ClusterIP、NodePort、Headless Service、HostNetwork、ExternalIPs，或者直接使用Pod网络。每种方法都有不同的适用场景，需要逐一分析。例如&…...

编程日记 2025/8/4 10:14:00

高性能边缘计算网关-高算力web组态PLC网关

高性能EG8200Pro边缘计算算力网关-超强处理能力样机申请测试：免费测试超30天（https://www.iotrouter.com/prototype/） 产品主要特点和特色功能设备概览与连接能力设备型号：EG8200P。主要特点： 支持多种工业协议&am…...

编程日记 2025/8/4 1:36:43

计算机视觉总结

以下是针对上述问题的详细解答，并结合代码示例进行说明： 1. 改进YOLOv5人脸检测模块，复杂光照场景准确率从98.2%提升至99.5% 优化具体过程：光照补偿：在数据预处理阶段，采用自适应光照补偿算法，对图像进行实时增强，以减少光照变化对人脸检测的影响。数据增强：在训练…...

编程日记 2025/8/4 7:02:15

【Golang】defer与recover的组合使用

在Go语言中，defer和recover是两个关键特性，通常结合使用以处理资源管理和异常恢复。以下是它们的核心应用场景及使用示例： 1. defer 的应用场景 defer用于延迟执行函数调用，确保在函数退出前执行特定操作。主要用途包括&#xff…...

编程日记 2025/8/4 6:07:27

Beyond Compare 4注册激活方法

Beyond Compare 4 注册码 --- BEGIN LICENSE KEY --- H1bJTd2SauPv5Garuaq0Ig43uqq5NJOEw94wxdZTpU-pFB9GmyPk677gJ vC1Ro6sbAvKR4pVwtxdCfuoZDb6hJ5bVQKqlfihJfSYZt-xVrVU270Ja hFbqTmYskatMTgPyjvv99CF2Te8ecYs2SPxyZAF0YwOCNOWmsyqN5y9t q2Kw2pjoiDs5gIH-uw5U49JzOB6otS7kT…...

编程日记 2025/7/31 1:36:55

[C++游戏开发基础]:构造函数浅析,8000+字长文

构造函数构造函数是一种特殊的成员函数,在创建非聚合类类型对象后会自动被调用。当定义一个非聚合类类型对象时,编译器会检查是否能找到一个可以访问的构造函数,该构造函数与调用者提供的初始化值(如果有的情况下)相匹配。如果找到一个可访问的匹配构造函数，将为…...

编程日记 2025/8/4 10:17:40

【Go】切片

知识点关键概念切片声明var slice []int初始化切片slice : []int{1,2,3}make() 创建切片make([]int, len, cap)获取长度和容量len(slice), cap(slice)追加元素slice append(slice, value)切片截取slice[start:end]（返回子切片）拷贝切片copy(dest, src)&…...

编程日记 2025/8/4 10:21:18

MySQL 设置允许远程连接完整指南：安全与效率并重

一、为什么需要远程连接MySQL？ 在分布式系统架构中，应用程序与数据库往往部署在不同服务器。例如： Web服务器（如NginxPHP）需要连接独立的MySQL数据库数据分析师通过BI工具直连生产库多服务器集群间的数据同步但直接…...

编程日记 2025/8/4 10:19:29

Cursor IDE 入门指南

什么是 Cursor? Cursor 是一款集成了 AI 功能的现代代码编辑器，基于 VSCode 开发，专为提高开发效率而设计。它内置强大的 AI 助手功能，能够理解代码、生成代码、解决问题，帮助开发者更快、更智能地完成编程任务。基础功能 1.…...

编程日记 2025/7/28 21:53:16

32.[前端开发-JavaScript基础]Day09-元素操作-window滚动-事件处理-事件委托

JavasScript事件处理 1 认识事件处理认识事件(Event) 常见的事件列表认识事件流 2 事件冒泡捕获事件冒泡和事件捕获事件捕获和冒泡的过程 3 事件对象event 事件对象 event常见的属性和方法事件处理中的this 4 EventTarget使用 EventTarget类 5 事件委托模式事件委托&am…...

编程日记 2025/8/4 10:12:45

【工具变量】中国各地级市是否属于“信息惠民国家试点城市”匹配数据（2010-2024年）

数据来源：国家等12部门联合发布的《关于加快实施信息惠民工程有关工作的通知》数据说明：内含原始文件和匹配结果，当试点城市在2014年及以后，赋值为1；试点城市在2014年之前或该城市从未实施信息惠民试点工程&#x…...

编程日记 2025/8/4 10:17:39

windows安装配置FFmpeg教程

1.先访问官网：https://www.gyan.dev/ffmpeg/builds/ 2.选择安装包Windows builds from gyan.dev 3. 下滑找到release bulids部分，选择ffmpeg-7.0.2-essentials_build.zip 4. 然后解压将bin目录添加path系统变量：\ffmpeg-7.0.2-essentials_bui…...

编程日记 2025/7/31 23:38:28

Wispr Flow，AI语言转文字工具

Wispr Flow是什么 Wispr Flow 是AI语音转文本工具，基于先进的AI技术，帮助用户在任何应用程序中实现快速语音转文字。 Wispr Flow支持100多种语言，具备自动编辑、上下文感知和低音量识别等功能，大幅提升写作和沟通效率。Wispr Fl…...

编程日记 2025/7/30 9:29:11

风暴潮、潮汐潮流模拟：ROMS模型如何精准预测海洋现象？

海洋数值模拟的崛起与 ROMS 的关键角色 🌊在海洋科学的浪潮中，海洋数值模拟正以迅猛之势崛起，成为科研与实际应用领域不可或缺的利器。ROMS（Regional Ocean Modeling System）作为其中的佼佼者，凭借其高效、…...

编程日记 2025/8/4 10:16:41

【Rust】集合的使用——Rust语言基础16

文章目录 1. 前言2. Vector2.1. 构建一个 vector2.2. 获取 vector 中的元素2.3. 遍历 vector2.4. 使用枚举来储存多种类型 3. String3.1. 新建字符串3.2. 更新字符串3.3. 字符串的内部结构3.3.1. 字符串如何访问内部元素？3.3.2. 字节、标量值和字形簇 3.4. 字符串 s…...

编程日记 2025/8/4 10:12:46

Kafka集成Debezium监听postgresql变更

下载postgres的插件：https://debezium.io/documentation/reference/2.7/install.html 2.7版本支持postgresql12数据库。 debezium-connector-postgres-2.7.4.Final-plugin.tar.gz 上传插件并解压 mkdir /usr/local/kafka/kafka_2.12-2.2.1/connector cd /usr/local…...

编程日记 2025/8/4 1:36:49

自动学习和优化过程，实现更加精准的预测和决策的智慧交通开源了

智慧交通视觉监控平台是一款功能强大且简单易用的实时算法视频监控系统。它的愿景是最底层打通各大芯片厂商相互间的壁垒，省去繁琐重复的适配流程，实现芯片、算法、应用的全流程组合，从而大大减少企业级应用约95%的开发成本。通过高效的实时视…...

编程日记 2025/8/4 10:16:42

第2.2节 Android Jacoco插件覆盖率采集

JaCoCo（Java Code Coverage）是一款开源的代码覆盖率分析工具，适用于Java和Android项目。它通过插桩技术统计测试过程中代码的执行情况，生成可视化报告，帮助开发者评估测试用例的有效性。在github上开源的项目&#xff…...

编程日记 2025/8/4 10:19:14

从零开始：使用 Cython + JNI 在 Android 上运行 Python 算法

1. 引言在 Android 设备上运行 Python 代码通常面临性能、兼容性和封装等挑战。尤其是当你希望在 Android 应用中使用 Python 编写的计算密集型算法时，直接运行 Python 代码可能导致较高的 CPU 占用和较差的性能。为了解决这个问题，我们可以使用 Cytho…...

编程日记 2025/7/31 17:25:00

开源软件许可证冲突的原因和解决方法

编程日记 2025/8/2 3:46:04

stratis，容器podman

一、stratis 1.stratis可以实现动态的在线扩容，lvm虽然也可以实现在线扩容，但是是需要人为的手动扩容。 2.stratis不需要手动格式化，自动会创建文件系统（默认是xfs） 1. 安装stratis软件包 yum list | grep stratis…...

编程日记 2025/7/29 10:05:52

解决用three.js展示n个叠加的stl模型文件错位的问题

加载stl时可以明显看到下面有一部分模型是错位的。将stl文件格式转化为glb 使用免费将 STL 转换为 GLB - ImageToStl 模型就没有错位了代码如下 <template><div ref"threeContainer" class"three-container"></div></template&…...

编程日记 2025/7/20 19:10:51

从零开始实现 C++ TinyWebServer 数据库连接池 SqlConnectPool详解

文章目录数据库连接池是什么？Web Server 中为什么需要数据库连接池？SqlConnectPool 成员变量实现 Init() 函数实现 ClosePool() 函数SqlConnectRAII 类SqlConnectPool 代码SqlConnectPool 测试从零开始实现 C TinyWebServer 项目总览项目源码数据库连…...

编程日记 2025/8/1 18:50:57

利用ffmpeg库实现音频AAC编解码

AAC‌（Advanced Audio Coding）是一种音频编码技术，出现于1997年，基于MPEG-2的音频编码技术。AAC具有高效的数据压缩能力和较高的音质，适用于各种音频应用场景。例如，在智能设备中，AAC技术被广泛…...

编程日记 2025/7/31 11:58:29

Vue + CSS实现渐变栅格进度条

进度条作为可视化大屏系统中展示数据状态的关键元素，其视觉效果直接影响用户的使用体验，而传统的进度条往往呈现出固定的样式，缺乏视觉吸引力。在这种场景下，一种基于Vue和CSS实现渐变栅格进度条的方法应运而生，该方法…...

编程日记 2025/7/24 7:12:05

算法模型从入门到起飞系列——背包问题（探索最大价值的掘金之旅）

文章目录前言一、背包问题溯源（动态规划）1.1 动态规划的概念1.2 动态规划的基本步骤1.3 动态规划的实际应用二、背包问题2.1 背包问题衍生2.2 0-1背包2.2.1 0-1背包描述2.2.2 0-1背包图解2.2.3 0-1背包代码刨析 2.3 完全背包2.3.1 完全背包描述2.3.2 完…...

编程日记 2025/8/3 14:13:07

蓝桥杯—迷宫(bfs)

一.题目分析:最短路径问题，给定一个迷宫，从左上角走到右下角，要求路径最短，并且要求字典序最小，也就是按照D，L，R，U，的搜索顺序去搜索，否则路径不是唯一的&am…...

编程日记 2025/7/28 23:27:03

【Android】安卓 Java下载ZIP文件并解压（笔记）

写在前面的话在这篇文章中，我们将详细讲解如何在 Android 中通过 Java 下载 ZIP 文件并解压，同时处理下载进度、错误处理以及优化方案。以下正文 1.权限配置在 AndroidManifest.xml 中，我们需要添加相应的权限来确保应用能够访问网络和设…...

编程日记 2025/8/2 18:43:01

清晰易懂的 PHP 安装与配置教程

初学者也能看懂的 PHP 安装与配置教程本教程将手把手教你如何在 Windows 系统上安装 PHP，并配置 Composer（PHP 的依赖管理工具）的缓存位置，即使你是零基础小白，也能轻松完成！ 一、准备工作操作系统&…...

编程日记 2025/7/31 13:25:30

Ceph集群2025（Squid版）快速对接K8S cephFS文件存储

ceph的块存储太简单了。所以不做演示查看集群创建一个 CephFS 文件系统 # ceph fs volume create cephfs01 需要创建一个子卷# ceph fs subvolume create cephfs01 my-subvol -----------------#以下全部自动创建好 # ceph fs ls name: cephfs01, metadata pool: c…...

编程日记 2025/8/3 16:41:44

Linux进程控制（四）之进程程序替换

文章目录进程程序替换单进程版程序替换替换原理多进程版程序替换替换函数函数解释小知识命名理解进程程序替换如果要让子进程执行与父进程完全不同的代码，就要进行进程程序替换。单进程版程序替换执行一个可执行文件 makefile mycommand:mycommand.cgcc -…...

编程日记 2025/8/4 7:47:52

python-selenium 爬虫由易到难

本质 python第三方库 selenium 空值浏览器驱动浏览器驱动控制浏览器推荐 edge 浏览器驱动（不容易遇到版本或者兼容性的问题） 驱动下载网址：链接: link 1、实战1 （1）安装 selenium 库 pip install selenium&#…...

编程日记 2025/8/1 1:57:56

希尔排序

希尔排序是一种改进的插入排序算法，它通过将原始数据分成多个子序列来改善插入排序的性能，每个子序列的元素间隔为 d（增量）。随着算法的进行，d 逐渐减小，最终减为 1，此时整个序列就被排序好了。…...

编程日记 2025/8/3 1:12:12

Pydantic Mixin：构建可组合的验证系统体系

title: Pydantic Mixin：构建可组合的验证系统体系 date: 2025/3/22 updated: 2025/3/22 author: cmdragon excerpt: Pydantic的Mixin模式通过继承组合实现校验逻辑复用，遵循以Mixin后缀命名、不定义初始化方法等设计原则。支持基础校验模块化封装与多策略组合，如电话号码…...

编程日记 2025/7/29 8:19:21

策略模式 vs. 工厂模式：对比与分析

相同点解耦思想两者都通过接口/抽象类将实现与调用方解耦，降低模块间的直接依赖。符合开闭原则新增策略或产品时，只需扩展新类，无需修改已有代码。封装变化策略模式封装算法的变化，工厂模式封装对象创建的变化。不同…...

编程日记 2025/7/30 18:25:39

有 prefixMap.put(0, 1) 的时候：

相关文章：