LeetCode_前缀和_滑动窗口_中等_930.和相同的二元子数组

清疚 2023-10-06 23:51 22阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

给你一个二元数组 nums ，和一个整数 goal ，请你统计并返回有多少个和为 goal 的非空子数组。

子数组是数组的一段连续部分。

**示例 1：**  
输入：nums = \[1,0,1,0,1\], goal = 2  
输出：4  
解释：  
有 4 个满足题目要求的子数组：\[1,0,1\]、\[1,0,1,0\]、\[0,1,0,1\]、\[1,0,1\]

**示例 2：**  
输入：nums = \[0,0,0,0,0\], goal = 0  
输出：15

**提示：**  
1 <= nums.length <= 3 \* 104  
nums\[i\] 不是 0 就是 1  
0 <= goal <= nums.length

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/binary-subarrays-with-sum

## 2.思路 ##

（1）前缀和  
常规想法是使用**前缀和数组**，即 preSum\[i\] 保存 nums\[0…i - 1\] 的前缀和，然后再使用两层 for 循环来遍历所有的子数组，并判断其元素总和是否为 goal，如果是，则 res++（初始值为 0，用于记录符合条件的子数组的个数）。遍历结束后直接返回 res 即可。但是需要注意的是该方法并未能充分利用题目数组 nums 的特点（即元素二元性，nums\[i\] 不是 0 就是 1），并且其时间复杂度为 O(n2)。

（2）前缀和 & 哈希表  
思路参考[本题官方题解][Link 1]。

（3）滑动窗口  
思路参考[本题官方题解][Link 1]。

## 3.代码实现（Java） ##

//思路1————前缀和
    class Solution {
        
        public int numSubarraysWithSum(int[] nums, int goal) {
        
            int res = 0;
            int length = nums.length;
            //preSum[i]:保存 nums[0...i - 1]的和
            int[] preSum = new int[length + 1];
            for (int i = 1; i < length + 1; i++) {
        
                preSum[i] = preSum[i - 1] + nums[i - 1];
            }
            for (int i = 0; i < length; i++) {
        
                for (int j = i + 1; j < length + 1; j++) {
        
                    //preSum[j] - preSum[i] 表示子数组 nums[i...j) 的元素和
                    if (preSum[j] - preSum[i] == goal) {
        
                        res++;
                    }
                }
            }
            return res;
        }
    }

//思路2————前缀和 & 哈希表
    class Solution {
        
        public int numSubarraysWithSum(int[] nums, int goal) {
        
            int sum = 0;
            Map<Integer, Integer> cnt = new HashMap<Integer, Integer>();
            int ret = 0;
            for (int num : nums) {
        
                cnt.put(sum, cnt.getOrDefault(sum, 0) + 1);
                sum += num;
                ret += cnt.getOrDefault(sum - goal, 0);
            }
            return ret;
        }
    }

//思路3————滑动窗口
    class Solution {
        
        public int numSubarraysWithSum(int[] nums, int goal) {
        
            int res = 0;
            int length = nums.length;
            int left1 = 0, left2 = 0, right = 0;
            int sum1 = 0, sum2 = 0;
            while (right < length) {
        
                sum1 += nums[right];
                while (left1 <= right && sum1 > goal) {
        
                    sum1 -= nums[left1];
                    left1++;
                }
                sum2 += nums[right];
                while (left2 <= right && sum2 >= goal) {
        
                    sum2 -= nums[left2];
                    left2++;
                }
                // left2 - left1 表示刚好符合以 right 为右边界的最短子数组时，左侧连接的 0 的个数加 1. 
                // 最短子数组本身就是一个解，每多一个 0 也是一个解
                res += left2 - left1;
                right++;
            }
            return res;
        }
    }

[Link 1]: https://leetcode.cn/problems/binary-subarrays-with-sum/solution/he-xiang-tong-de-er-yuan-zi-shu-zu-by-le-5caf/