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

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 * 10⁴
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(n²)。

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

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

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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

//思路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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

//思路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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26