560. 和为K的子数组

560. 和为K的子数组

确定区间 [ i , j ] [i, j] [i,j]，求改区间的和，如果区间的和等于 K K K，那么次数加一，显然，该算法的时间复杂度为 O ( n 3 ) O(n^3) O(n3)。会超时。

事实上，我们可以在 O ( 1 ) O(1) O(1) 的时间内求出区间 [ i , j ] [i, j] [i,j] 的和。
一种方式是使用数组存放 n u m s nums nums 数组的前缀和，即该数组为 S S S, 那么区间 [ i , j ] [i, j] [i,j]的和为 S [ j ] − S [ i − 1 ] S[j]-S[i-1] S[j]−S[i−1].
另一种方式是，当我们知道区间 [ i , j − 1 ] [i, j-1] [i,j−1]的和时，我们可以在 O ( 1 ) O(1) O(1) 的时间内求解出区间 [ i , j ] [i, j] [i,j]的和。

显然，第二种方式优于第一种方式。下面是代码。

class Solution {
public:
    int subarraySum(vector& nums, int k) {
        int ret = 0;
        int n = nums.size();
        for (int i = 0; i < n; i ++){
            int sum = 0;
            for (int j = i; j < n; j ++){
                sum += nums[j];
                if (sum == k){
                    ret ++;
                }
            }
        }
        return ret;
    }
};

复杂度分析：

• 时间复杂度： O ( n 2 ) O(n^2) O(n2)
• 空间复杂度： O ( 1 ) O(1) O(1)

不幸的是，这种方式仍然会TLE。

我们记 n u m s nums nums 数组的前缀和为 S S S. 那么相当于求解 ( i , j ) (i, j) (i,j) 的个数，其中， S [ j ] − S [ i − 1 ] = k S[j] - S[i-1] = k S[j]−S[i−1]=k.

由于 i ≤ j i le j i≤j, 那么， j j j 严格大于 i − 1 i-1 i−1， 那么我们在求解 S [ j ] S[j] S[j]时， S [ i − 1 ] S[i-1] S[i−1] 必然已经求解完成。

也就是说，当我们求解到 S [ j ] S[j] S[j] 时，我们要 尽快地 知道有多少个 i − 1 i-1 i−1 能够满足 S [ j ] − k = S [ i − 1 ] S[j] - k = S[i-1] S[j]−k=S[i−1]。

我们可以使用 unordered_map 来存储 【前缀和，数量】，那么可以在线性时间内尽快地求解问题。

当写出代码时：

class Solution {
public:
    int subarraySum(vector& nums, int k) {
        int ret = 0;
        int n = nums.size();
        unordered_map umap;
        int sum = 0;
        for (auto item : nums){
            sum += item;
            ret += umap[sum-k];
            umap[sum] += 1;
        }

        return ret;
    }
};

发现，测试样例 n u m s = [ 1 , 1 , 1 ] nums=[1,1,1] nums=[1,1,1], k = 2 k=2 k=2 得到的结果是 1. 经过模拟发现，当 s u m sum sum求解后，刚好有 s u m = k sum=k sum=k，而此时umap[sum-k]=umap[0]=0，因此，umap[0]=1.

经过上述分析，可以写出AC代码：

class Solution {
public:
    int subarraySum(vector& nums, int k) {
        int ret = 0;
        int n = nums.size();
        unordered_map umap;
        umap[0] = 1;
        int sum = 0;
        for (auto item : nums){
            sum += item;
            ret += umap[sum-k];
            umap[sum] += 1;
        }

        return ret;
    }
};

复杂度分析：

• 时间复杂度： O ( n ) O(n) O(n)
• 空间复杂度： O ( n ) O(n) O(n)

2021.07.06 21:35

2021.10.5 10:59
七月份的文章，十月份发，我真是，懒惰他妈给懒惰开门——懒到家了。