560 和为k的子数组
暴力解法
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int n = nums.size();
int res = 0;
for(int i = 0; i < n; i++){
int sum = 0;
for(int j = i; j < n; j++){
sum += nums[j];
if(sum == k)
res++;
}
}
return res;
}
};
时间复杂度:\(O(n^2)\)
空间复杂度:\(O(1)\)
优化版
题外话:这道题看到连续序列可能会想用滑动窗口
但是滑动窗口通常用于记录窗口内的最大最小值 或 子串长度
在本题中,k值可以为正数,也可以为负数,这意味着我们不一定求的是最值,使用滑动窗口无法求解
在暴力解法中,我们发现每次枚举nums[i]后,都会循环遍历nums[j]计算sum,这种计算子数组的和可以用前缀和优化
前缀和:我们想知道[j, i]的和,就可以使用前缀和pre[i] - pre[j - 1]计算
在本题中,我们想知道区间和为k数组的个数,我们当然可以遍历每个元素i,获得pre[i],但问题是我们不知道什么时候区间和等于k,即我们无法知道下标j
我们假设已经找到了j,那么有pre[i] - pre[j - 1] == k,我们发现pre[j - 1]可以用pre[i] - k代替,也就是我们不需要知道j具体是多少,只需要找出前缀和为pre[i] - k的数组即可
前缀和为pre[i] - k 与 区间和为k 可是完全不同的概念
- 或许你会说前缀和为
pre[i] - k,需要从0到i依次遍历寻找;区间和为k,也需要从i到0依次遍历寻找,都是\(O(n)\)时间复杂度 - 但是注意
pre[i]与pre[i] - k的关系,当我们得到了pre[i],说明我们已经得到了pre[i] - k,这两者都是通过前缀和计算得到的,而前缀和计算是遍历过程中得到的,因此我们可以维护一个哈希表,计算一次前缀和就将结果放入哈希表,那么当我们得到了pre[i],我们可以通过\(O(1)\)时间复杂度获得pre[i] - k的个数
最后,从左往右边更新边计算的时候已经保证了hashMap[pre[i]−k] 里记录的 pre[j] 的下标范围是 0≤j≤i 。同时,由于pre[i] 的计算只与前一项的答案有关,因此我们可以不用建立 pre 数组,直接用 pre 变量来记录 pre[i−1] 的答案即可。
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
// key记录值sum[i] - k,value记录个数
unordered_map<int,int> hashMap;
int n = nums.size();
int pre = 0;
int count = 0;
// 这一步不能省
// 因为pre == k的时候一定有解
// 从前缀和为0的时候开始
hashMap[0] = 1;
// sum[i] - sum[j - 1] = k
// 即sum[j - 1] = sum[i] - k
// 此处的pre就是sum[i]
for(int i = 0; i < n; i++){
pre += nums[i];
auto it = hashMap.find(pre - k);
if(it != hashMap.end())
count += it->second;
// 记录前缀和为pre的个数
hashMap[pre]++;
}
return count;
}
};
时间复杂度:\(O(n)\)
空间复杂度:\(O(n)\)