LeetCode930-和相同的二元子数组

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/binary-subarrays-with-sum/

中文链接：https://leetcode-cn.com/problems/binary-subarrays-with-sum/

题目详述

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

示例：

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

提示：

  1. A.length <= 30000
  2. 0 <= S <= A.length
  3. A[i] 为 0 或 1

题目详解

  • LeetCode560-和为K的子数组 是本题的通解，可以直接套用。
  • 对于这类与子数组和有关的问题，在很多时候，可以通过求前缀和做差来解答。
  • 注意，一般在 0 位置要特殊处理。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class LeetCode_00930 {

    public int numSubarraysWithSum(int[] A, int S) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        int res = 0;
        int s = 0;
        for (int a : A) {
            s += a;
            res += map.getOrDefault(s - S, 0);
            map.put(s, map.getOrDefault(s, 0) + 1);
        }
        return res;
    }
}

另外，由于数组元素只含 0 和 1，可以用一个数组作为哈希表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class LeetCode_00930 {

    public int numSubarraysWithSum(int[] A, int S) {
        int[] map = new int[A.length + 1];
        map[0] = 1;
        int res = 0;
        int s = 0;
        for (int a : A) {
            s += a;
            if (s >= S) {
                res += map[s - S];
            }
            ++map[s];
        }
        return res;
    }
}