和相同的二元子数组
方法一：哈希表
思路及算法
假设原数组的前缀和数组为 \textit{sum}，且子数组 (i,j] 的区间和为 \textit{goal}，那么 \textit{sum}[j]-\textit{sum}[i]=\textit{goal}。因此我们可以枚举 j ，每次查询满足该等式的 i 的数量。
具体地，我们用哈希表记录每一种前缀和出现的次数，假设我们当前枚举到元素 \textit{nums}[j]，我们只需要查询哈希表中元素 \textit{sum}[j]-\textit{goal} 的数量即可，这些元素的数量即对应了以当前 j 值为右边界的满足条件的子数组的数量。最后这些元素的总数量即为所有和为 \textit{goal} 的子数组数量。
在实际代码中，我们实时地更新哈希表，以防止出现 i \geq j 的情况。
代码
class Solution {
public:
int numSubarraysWithSum(vector<int>& nums, int goal) {
int sum = 0;
unordered_map<int, int> cnt;
int ret = 0;
for (auto& num : nums) {
cnt[sum]++;
sum += num;
ret += cnt[sum - goal];
}
return ret;
}
};
复杂度分析
- 时间复杂度：O(n)，其中 n 为给定数组的长度。对于数组中的每个元素，我们至多只需要插入到哈希表中中一次。
- 空间复杂度：O(n)，其中 n 为给定数组的长度。哈希表中至多只存储 O(n) 个元素。
方法二：滑动窗口
思路及算法
注意到对于方法一中每一个 j，满足 \textit{sum}[j]-\textit{sum}[i]=\textit{goal} 的 i 总是落在一个连续的区间中，i 值取区间中每一个数都满足条件。并且随着 j 右移，其对应的区间的左右端点也将右移，这样我们即可使用滑动窗口解决本题。
具体地，我们令滑动窗口右边界为 \textit{right}，使用两个左边界 \textit{left}_1 和 \textit{left}_2 表示左区间 [\textit{left}_1,\textit{left}_2)，此时有 \textit{left}_2-\textit{left}_1 个区间满足条件。
在实际代码中，我们需要注意 \textit{left}_1 \leq \textit{left}_2 \leq \textit{right} + 1，因此需要在代码中限制 \textit{left}_1 和 \textit{left}_2 不超出范围。
代码
class Solution {
public:
int numSubarraysWithSum(vector<int>& nums, int goal) {
int n = nums.size();
int left1 = 0, left2 = 0, right = 0;
int sum1 = 0, sum2 = 0;
int ret = 0;
while (right < n) {
sum1 += nums[right];
while (left1 <= right && sum1 > goal) {
sum1 -= nums[left1];
left1++;
}
sum2 += nums[right];
while (left2 <= right && sum2 >= goal) {
sum2 -= nums[left2];
left2++;
}
ret += left2 - left1;
right++;
}
return ret;
}
};
复杂度分析
- 时间复杂度：O(n)，其中 n 为给定数组的长度。我们至多只需要遍历一次该数组。
- 空间复杂度：O(1)。我们只需要常数的空间保存若干变量。