算法题 和相同的二元子数组

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个非空子数组。

算法思路

前缀和 + 哈希表：

1. 计算前缀和数组，其中prefixSum[i]表示nums[0...i-1]的和
2. 对于每个位置i，需要找到有多少个位置j < i满足：prefixSum[i] - prefixSum[j] = goal
3. 即：prefixSum[j] = prefixSum[i] - goal
4. 使用哈希表记录每个前缀和出现的次数，可以在O(1)时间内查询

滑动窗口（goal >= 0）：

1. 由于数组只包含0和1，子数组和具有单调性
2. 可以使用滑动窗口计算和小于等于goal的子数组数量
3. 结果 = 和小于等于goal的数量 - 和小于等于goal-1的数量

暴力：

1. 枚举所有可能的子数组
2. 计算每个子数组的和
3. 统计和等于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;}}

算法分析

算法过程

输入：nums = [1,0,1,0,1], goal = 2

方法一：

1. 初始化：prefixCount = {0:1},currentSum = 0,result = 0
2. num=1:currentSum=1,target=1-2=-1（不存在）,prefixCount={0:1,1:1}
3. num=0:currentSum=1,target=1-2=-1（不存在）,prefixCount={0:1,1:2}
4. num=1:currentSum=2,target=2-2=0（存在，计数+1）,result=1,prefixCount={0:1,1:2,2:1}
5. num=0:currentSum=2,target=2-2=0（存在，计数+1）,result=2,prefixCount={0:1,1:2,2:2}
6. num=1:currentSum=3,target=3-2=1（存在，计数+2）,result=4,prefixCount={0:1,1:2,2:2,3:1}
7. 返回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}

关键点

1. 前缀和：

   • 子数组和 = prefixSum[j] - prefixSum[i]
   • 转化为查找问题：对于每个j，找有多少个i满足条件

2. 滑动窗口：

   • 数组元素非负（这里是0和1）
   • 利用单调性：窗口扩大时和增加，窗口缩小时和减少

3. 哈希表初始化：

   • 必须初始化prefixCount.put(0, 1)
   • 对应空数组的前缀和，处理从索引0开始的子数组

常见问题

1. 为什么前缀和要初始化prefixCount[0] = 1？

   • 当子数组从索引0开始时，需要prefixSum[j] - prefixSum[-1] = goal
   • 而prefixSum[-1]定义为0，所以需要记录前缀和0的出现次数

2. 滑动窗口？

   • 数组元素非负，所以子数组和具有单调性