LeetCode 930 和相同的二元子数组 - 前缀和解法
🟡 中等 https://leetcode.cn/problems/binary-subarrays-with-sum/description/
思路
可以用滑动窗口解决：[19-930和相同的二元子数组](../02 滑动窗口/LeetCode 930 和相同的二元子数组 - 滑动窗口解法.md)。
这里记录的是前缀和写法，整体更直接。
class Solution {
public:
int numSubarraysWithSum(vector<int>& nums, int goal) {
unordered_map<int, int> hash_map;
int sum1 = 0;
int res = 0;
for (int i = 0; i < nums.size(); i++) {
hash_map[sum1]++;
sum1 += nums[i];
res += hash_map[sum1 - goal];
}
return res;
}
};
小tips
上面的代码通过“先记录旧前缀和，再更新新前缀和”来处理 0 前缀。如果改成提前设定 hash_map[0] = 1，则通常要配合显式查找逻辑，例如：
#include <vector>
#include <unordered_map>
using namespace std;
class Solution {
public:
int numSubarraysWithSum(vector<int>& nums, int goal) {
unordered_map<int, int> hash_map;
hash_map[0] = 1; // Handle the case where the sum itself is equal to goal
int sum1 = 0;
int res = 0;
for (int num : nums) {
sum1 += num;
if (hash_map.find(sum1 - goal) != hash_map.end()) {
res += hash_map[sum1 - goal];
}
hash_map[sum1]++;
}
return res;
}
};