跳转至

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)\)