LeetCode 930 和相同的二元子数组 - 滑动窗口解法
🟡 中等 https://leetcode.cn/problems/binary-subarrays-with-sum/description/
思路
首先长度无限制，但是窗口内的元素和有限制。枚举右端点，左侧遍历保存结果。
左侧如果是0，那么需要找到第一个1。
class Solution {
public:
int numSubarraysWithSum(vector<int>& nums, int goal) {
int left = 0;
int sum = 0;
int res = 0;
for (int i = 0; i < nums.size(); i++) {
sum += nums[i];
while (sum > goal && left < i) {
sum -= nums[left];
left++;
}
if (sum == goal) {
//找到第一个1
int tmp = left;
while (nums[tmp] == 0 && tmp < i) {
tmp++;
}
res += (tmp - left + 1);
}
}
return res;
}
};
注意到，每次左侧要向右试探性的遍历，因此，可以使用更加简洁的方法 前缀和
用hash_map记录前缀和出现的次数，每次向右扩展一个新元素时就检查 hash_map[current_sum-goal] 的次数，加到res 中。
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;
}
};