930. 和相同的二元子数组
问题描述
给你一个二元数组nums和一个整数goal，请你统计并返回有多少个非空连续子数组的和等于goal。
示例：
输入: nums = [1,0,1,0,1], goal = 2 输出: 4 解释: 有4个满足要求的子数组: [1,0,1], [1,0,1,0], [0,1,0,1], [1,0,1] 输入: nums = [0,0,0,0,0], goal = 0 输出: 15 解释: 所有子数组的和都是0，总共有15个非空子数组。算法思路
前缀和 + 哈希表：
- 计算前缀和数组，其中
prefixSum[i]表示nums[0...i-1]的和 - 对于每个位置
i，需要找到有多少个位置j < i满足：prefixSum[i] - prefixSum[j] = goal - 即：
prefixSum[j] = prefixSum[i] - goal - 使用哈希表记录每个前缀和出现的次数，可以在O(1)时间内查询
滑动窗口（goal >= 0）：
- 由于数组只包含0和1，子数组和具有单调性
- 可以使用滑动窗口计算和小于等于
goal的子数组数量 - 结果 = 和小于等于
goal的数量 - 和小于等于goal-1的数量
暴力：
- 枚举所有可能的子数组
- 计算每个子数组的和
- 统计和等于
goal的数量
代码实现
方法一：前缀和 + 哈希表
classSolution{/** * 使用前缀和 + 哈希表统计和为goal的子数组数量 * * @param nums 二元数组（只包含0和1） * @param goal 目标和 * @return 和为goal的非空连续子数组数量 */publicintnumSubarraysWithSum(int[]nums,intgoal){// 哈希表存储前缀和及其出现次数Map<Integer,Integer>prefixCount=newHashMap<>();// 初始化：前缀和为0出现1次（空数组）prefixCount.put(0,1);intcurrentSum=0;// 当前前缀和intresult=0;// 结果计数for(intnum:nums){currentSum+=num;// 查找是否存在前缀和 = currentSum - goalinttarget=currentSum-goal;if(prefixCount.containsKey(target)){result+=prefixCount.get(target);}// 更新当前前缀和的计数prefixCount.put(currentSum,prefixCount.getOrDefault(currentSum,0)+1);}returnresult;}}方法二：滑动窗口
classSolution{/** * 使用滑动窗口 * * @param nums 二元数组 * @param goal 目标和 * @return 和为goal的子数组数量 */publicintnumSubarraysWithSum(int[]nums,intgoal){if(goal==0){// 特殊处理goal=0的情况returncountZeroSubarrays(nums);}// 计算和 <= goal 的子数组数量intatMostGoal=countSubarraysAtMost(nums,goal);// 计算和 <= goal-1 的子数组数量intatMostGoalMinusOne=countSubarraysAtMost(nums,goal-1);// 和恰好等于goal的数量 = atMostGoal - atMostGoalMinusOnereturnatMostGoal-atMostGoalMinusOne;}/** * 计算和小于等于target的子数组数量 */privateintcountSubarraysAtMost(int[]nums,inttarget){if(target<0)return0;intleft=0;intcurrentSum=0;intcount=0;for(intright=0;right<nums.length;right++){currentSum+=nums[right];// 收缩窗口直到和 <= targetwhile(currentSum>target){currentSum-=nums[left];left++;}// 以right结尾的满足条件的子数组数量 = right - left + 1count+=right-left+1;}returncount;}/** * 专门处理goal=0的情况：统计连续0的子数组数量 */privateintcountZeroSubarrays(int[]nums){intcount=0;intconsecutiveZeros=0;for(intnum:nums){if(num==0){consecutiveZeros++;count+=consecutiveZeros;// 连续k个0可以形成k*(k+1)/2个子数组}else{consecutiveZeros=0;}}returncount;}}方法三：暴力
classSolution{/** * 暴力：枚举所有子数组 */publicintnumSubarraysWithSum(int[]nums,intgoal){intcount=0;intn=nums.length;for(inti=0;i<n;i++){intsum=0;for(intj=i;j<n;j++){sum+=nums[j];if(sum==goal){count++;}elseif(sum>goal){// 由于数组只包含0和1，后续和只会更大break;}}}returncount;}}算法分析
| 方法 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 前缀和+哈希表 | O(n) | O(n) |
| 滑动窗口 | O(n) | O(1) |
| 暴力 | O(n²) | O(1) |
算法过程
输入：nums = [1,0,1,0,1], goal = 2
方法一：
- 初始化：
prefixCount = {0:1},currentSum = 0,result = 0 num=1:currentSum=1,target=1-2=-1（不存在）,prefixCount={0:1,1:1}num=0:currentSum=1,target=1-2=-1（不存在）,prefixCount={0:1,1:2}num=1:currentSum=2,target=2-2=0（存在，计数+1）,result=1,prefixCount={0:1,1:2,2:1}num=0:currentSum=2,target=2-2=0（存在，计数+1）,result=2,prefixCount={0:1,1:2,2:2}num=1:currentSum=3,target=3-2=1（存在，计数+2）,result=4,prefixCount={0:1,1:2,2:2,3:1}- 返回
4
测试用例
publicstaticvoidmain(String[]args){Solutionsolution=newSolution();// 测试用例1：标准示例int[]nums1={1,0,1,0,1};System.out.println("Test 1: "+solution.numSubarraysWithSum(nums1,2));// 4// 测试用例2：全0数组int[]nums2={0,0,0,0,0};System.out.println("Test 2: "+solution.numSubarraysWithSum(nums2,0));// 15// 测试用例3：全1数组int[]nums3={1,1,1,1,1};System.out.println("Test 3: "+solution.numSubarraysWithSum(nums3,3));// 3// 测试用例4：单元素int[]nums4={1};System.out.println("Test 4: "+solution.numSubarraysWithSum(nums4,1));// 1System.out.println("Test 4: "+solution.numSubarraysWithSum(nums4,0));// 0// 测试用例5：goal大于总和int[]nums5={1,0,1};System.out.println("Test 5: "+solution.numSubarraysWithSum(nums5,5));// 0// 测试用例6：goal为0，混合数组int[]nums6={1,0,0,1,0};System.out.println("Test 6: "+solution.numSubarraysWithSum(nums6,0));// 4// 连续0的子数组：[0], [0], [0,0], [0] → 4个// 测试用例7：goal为负数int[]nums7={1,0,1};System.out.println("Test 7: "+solution.numSubarraysWithSum(nums7,-1));// 0// 测试用例8：大数组int[]nums8=newint[1000];Arrays.fill(nums8,1);System.out.println("Test 8: "+solution.numSubarraysWithSum(nums8,500));// 501// 测试用例9：交替数组int[]nums9={1,0,1,0,1,0};System.out.println("Test 9: "+solution.numSubarraysWithSum(nums9,2));// 6// 测试用例10：边界情况int[]nums10={0};System.out.println("Test 10: "+solution.numSubarraysWithSum(nums10,0));// 1}关键点
前缀和：
- 子数组和 = prefixSum[j] - prefixSum[i]
- 转化为查找问题：对于每个j，找有多少个i满足条件
滑动窗口：
- 数组元素非负（这里是0和1）
- 利用单调性：窗口扩大时和增加，窗口缩小时和减少
哈希表初始化：
- 必须初始化
prefixCount.put(0, 1) - 对应空数组的前缀和，处理从索引0开始的子数组
- 必须初始化
常见问题
为什么前缀和要初始化
prefixCount[0] = 1？- 当子数组从索引0开始时，需要
prefixSum[j] - prefixSum[-1] = goal - 而
prefixSum[-1]定义为0，所以需要记录前缀和0的出现次数
- 当子数组从索引0开始时，需要
滑动窗口？
- 数组元素非负，所以子数组和具有单调性
