和相同的二元子数组 图解题解

这道题到底在问什么

输入

nums=[1,0,1,0,1], goal=2

输出

4

输入

nums=[0,0,0,0,0], goal=0

输出

15 （所有非空子数组）

最优解：一步一步想明白

1. 3记住「子数组和=goal ⟺ 找更早的前缀和=当前前缀和−goal」，下面每帧都在套它。
2. 4开局：前缀和为 0、答案为 0。表里先放一个「前缀和 0 出现 1 次」——它代表从头开始的子数组（空前缀），别漏。
3. 5读到第 0 个（1），前缀和变成 1。要找前缀和 = 1−2 = -1：表里没有，这一步贡献 0。
4. 6结算：答案加 0，变成 0。再把当前前缀和 1 记进表（高亮行，现 1 次），供后面的元素来匹配。
5. 7读到第 1 个（0），前缀和变成 1。要找前缀和 = 1−2 = -1：表里没有，这一步贡献 0。
6. 8结算：答案加 0，变成 0。再把当前前缀和 1 记进表（高亮行，现 2 次），供后面的元素来匹配。
7. 9读到第 2 个（1），前缀和变成 2。要找前缀和 = 2−2 = 0：表里有 1 个（高亮行），说明有 1 个以这里结尾、和为 2 的子数组。
8. 10结算：答案加 1，变成 1。再把当前前缀和 2 记进表（高亮行，现 1 次），供后面的元素来匹配。
9. 11读到第 3 个（0），前缀和变成 2。要找前缀和 = 2−2 = 0：表里有 1 个（高亮行），说明有 1 个以这里结尾、和为 2 的子数组。
10. 12结算：答案加 1，变成 2。再把当前前缀和 2 记进表（高亮行，现 2 次），供后面的元素来匹配。
11. 13读到第 4 个（1），前缀和变成 3。要找前缀和 = 3−2 = 1：表里有 2 个（高亮行），说明有 2 个以这里结尾、和为 2 的子数组。
12. 14结算：答案加 2，变成 4。再把当前前缀和 3 记进表（高亮行，现 1 次），供后面的元素来匹配。
13. 15读到第 5 个（1），前缀和变成 4。要找前缀和 = 4−2 = 2：表里有 2 个（高亮行），说明有 2 个以这里结尾、和为 2 的子数组。
14. 16结算：答案加 2，变成 6。再把当前前缀和 4 记进表（高亮行，现 1 次），供后面的元素来匹配。
15. 17读到第 6 个（0），前缀和变成 4。要找前缀和 = 4−2 = 2：表里有 2 个（高亮行），说明有 2 个以这里结尾、和为 2 的子数组。
16. 18结算：答案加 2，变成 8。再把当前前缀和 4 记进表（高亮行，现 2 次），供后面的元素来匹配。
17. 19读到第 7 个（1），前缀和变成 5。要找前缀和 = 5−2 = 3：表里有 1 个（高亮行），说明有 1 个以这里结尾、和为 2 的子数组。
18. 20结算：答案加 1，变成 9。再把当前前缀和 5 记进表（高亮行，现 1 次），供后面的元素来匹配。
19. 21读到第 8 个（0），前缀和变成 5。要找前缀和 = 5−2 = 3：表里有 1 个（高亮行），说明有 1 个以这里结尾、和为 2 的子数组。
20. 22结算：答案加 1，变成 10。再把当前前缀和 5 记进表（高亮行，现 2 次），供后面的元素来匹配。
21. 23读到第 9 个（1），前缀和变成 6。要找前缀和 = 6−2 = 4：表里有 2 个（高亮行），说明有 2 个以这里结尾、和为 2 的子数组。
22. 24结算：答案加 2，变成 12。再把当前前缀和 6 记进表（高亮行，现 1 次），供后面的元素来匹配。
23. 25全程扫完，一共数到 12 个和为 2 的连续子数组。靠的是「每到一个位置，就用哈希表 O(1) 查有多少个匹配的旧前缀和」，整体一遍 O(n)。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from typing import List
from collections import defaultdict
class Solution:
    def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:
        count = defaultdict(int)
        count[0] = 1
        prefix = ans = 0
        for x in nums:
            prefix += x
            ans += count[prefix - goal]
            count[prefix] += 1
        return ans

#include <unordered_map>
#include <vector>
using namespace std;
class Solution {
public:
    int numSubarraysWithSum(vector<int>& nums, int goal) {
        unordered_map<int,int> count;
        count[0] = 1;
        int prefix = 0, ans = 0;
        for (int x : nums) {
            prefix += x;
            if (count.count(prefix - goal)) ans += count[prefix - goal];
            count[prefix]++;
        }
        return ans;
    }
};

import java.util.*;
class Solution {
    public int numSubarraysWithSum(int[] nums, int goal) {
        Map<Integer,Integer> count = new HashMap<>();
        count.put(0, 1);
        int prefix = 0, ans = 0;
        for (int x : nums) {
            prefix += x;
            ans += count.getOrDefault(prefix - goal, 0);
            count.put(prefix, count.getOrDefault(prefix, 0) + 1);
        }
        return ans;
    }
}

复杂度

面试官可能追问