LeetCode 560 Subarray Sum Equals K
概述
https://leetcode.com/problems/subarray-sum-equals-k/
滑动窗口法（无法处理有负值的情况）
从左向右遍历数组，当下一个元素加入窗口后发现值超出，就抛弃掉最左边的元素，然后继续。
历次 WA 的原因：
- 没有对 l 和 r 的大小关系做检查，导致 case k == 0，nums = [1] 失败；
- 没有想到输入是可以为负数，负值的出现使得合法的子窗口可以嵌套，我们原本的思路是错误的。
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int count = 0;
int l = 0; // the case the first element is bigger than k
int sum = 0;
for (int r = 0; r < nums.size(); r ++) {
sum += nums[r];
if (sum == k) {
count ++;
} else if (sum < k) {
continue;
} else { // sum > k
while (sum > k) {
sum -= nums[l];
l ++;
}
if (sum == k && l <= r) count ++; // the case k == 0 && nums = [1]
}
}
return count;
}
};
起始点结束点暴力遍历法
双层 for 循环遍历所有可能的起始点和结束点。
O(n^2) 的时间复杂度。
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int count = 0;
for (int l = 0; l < nums.size(); l ++) {
int sum = 0;
for (int r = l; r < nums.size(); r ++) {
sum += nums[r];
if (sum == k) count ++;
}
}
return count;
}
};
TLE 了。
中间节点暴力遍历法
中间节点可以是一个，也可以是两个。
由于这次有两个嵌套 for 循环，因此这次更早 TLE 了。
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int count = 0;
for (int m = 0; m < nums.size(); m ++) {
int sum = nums[m];
if (sum == k) count ++;
for (int d = 1; m - d >= 0 && m + d < nums.size(); d ++) {
sum += nums[m - d] + nums[m + d];
if (sum == k) count ++;
}
}
for (int m = 0; m < nums.size() - 1; m ++) {
int sum = nums[m] + nums[m + 1];
if (sum == k) count ++;
for (int d = 1; m - d >= 0 && m + 1 + d < nums.size(); d ++) {
sum += nums[m - d] + nums[m + 1 + d];
if (sum == k) count ++;
}
}
return count;
}
};
前缀和数组
https://labuladong.gitee.io/algo/2/21/56/
构造一个前缀和矩阵
我们没有必要构造前缀和矩阵啊喂，前缀和向量足够了。
注意，实现的时候 sums[i] 里存的值不包括 nums[i]，务必注意 i 与 j 的范围。
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
vector<int> sums(nums.size() + 1, 0);
for (int i = 0; i < nums.size(); i ++) {
sums[i + 1] = sums[i] + nums[i];
}
int count = 0;
for (int i = 0; i < nums.size(); i ++) {
for (int j = i + 1; j <= nums.size(); j ++) {
if (sums[j] - sums[i] == k) count ++;
}
}
return count;
}
};
然后我们就再次 TLE 了，时间复杂度也依然是 O(n^2)。
我们可以用一个 map 记录 sums[i] + k 的出现次数，这样就可以一次遍历解决问题。
注意里面 count 可不是加 1 哦，而是直接加上历史出现个数。
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
vector<int> sums(nums.size() + 1, 0);
for (int i = 0; i < nums.size(); i ++) {
sums[i + 1] = sums[i] + nums[i];
}
int count = 0;
unordered_map<int, int> m;
for (int i = 0; i <= nums.size(); i ++) {
if (m.count(sums[i]) != 0) {
count += m[sums[i]];
}
m[sums[i] + k] += 1;
}
return count;
}
};
更进一步地，我们可以合并两个 for 循环：
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int count = 0;
unordered_map<int, int> m;
for (int i = 0; i <= nums.size(); i ++) {
if (i < nums.size()) sums[i + 1] = sums[i] + nums[i];
if (m.count(sums[i]) != 0) {
count += m[sums[i]];
}
m[sums[i] + k] += 1;
}
return count;
}
};
更进一步地，我们可以取代 sums 数组，此时时间复杂度 O(n)，空间复杂度 O(n)（map 省不掉）：
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
vector<int> sums(nums.size() + 1, 0);
int count = 0;
unordered_map<int, int> m;
int currentSum = 0, nextSum = 0;
for (int i = 0; i <= nums.size(); i ++) {
currentSum = nextSum;
if (i < nums.size()) nextSum = currentSum + nums[i];
if (m.count(currentSum) != 0) {
count += m[currentSum];
}
m[currentSum + k] += 1;
}
return count;
}
};