和相同的二元子数组

  1. 先算前缀和
  2. 统计每一种前缀和出现的次数
  3. 遍历 nums，查询哈希表中元素 sum[j] − goal 的数量，进行累加
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
 public:
  int numSubarraysWithSum(vector<int>& nums, int goal) {
    vector<int> s(nums.size() + 1);
    int ans = 0;
    for (int i = 1; i <= nums.size(); i++) {
      s[i] = s[i - 1] + nums[i - 1];
    }
    // 用哈希表记录每一种前缀和 s[i] 出现的次数
    unordered_map<int, int> mp;
    mp[0] = 1;
    // s[r] - s[l-1] = goal
    // s[l-1] = s[r] - goal
    for (int i = 0; i < nums.size(); i++) {
      int l = s[i + 1] - goal;
      ans += mp[l];
      mp[r]++;
    }
    return ans;
  }
};