560.和为k的子数组

发表于： 分类于：
字数： 1116 阅读：≈ 3分钟

🦺 560.和为k的子数组

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的连续子数组的个数 。

子数组是数组中元素的连续非空序列。

思路

基本思想

为了找出所有和为k的连续子数组，可以依次从每一个元素出发， 依次累加之后的元素，一旦能够形成一个k，当前子数组就能符合要求，并且当前子数组符合要求之后，还需要继续遍历，否则会漏掉情况，例如数组为[1,1,,-1,1]，k=2，那么子数组[1,1]符合要求，且[1,1,-1,1]也符合要求

这样从每一个元素出发搜索的代码为：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    //可以尝试滑动窗口
    int subarraySum(vector<int>& nums, int k) {
        //暴力法,会超时
        //从每个数出发，从而找出所有的和为k的组合
        int res=0;
        for(int i=0;i<nums.size();++i){
            int sum=0;
            for(int j=i;j<nums.size();++j){
                sum+=nums[j];
                //一旦能够形成一个合法的子数组就记录
                if(sum==k)
                    res+=1;
            }
        }
        return res;
    }
};

但是这样做会超时，因为时间复杂度为O(N)，所以需要找到另外的办法

超时的原因是因为从每一个元素出发，都需要遍历所有的求和结果，才知道当前元素出发的子数组中有哪些是合法的，这是需要改进的点

定义 pre[i] 为 [0..i] 里所有数的和，也就是范围[0…i]中所有元素相加的结果是pre[i],而且per[i]可以由pre[i-1]推导得到： $$ pre[i]=pre[i-1]+nums[i] $$ 所以当范围[i,j]中的元素相加为k时，可以表示为： $$ pre[j]-pre[i]=k $$ 进一步当当前元素总和为sum时，我们只需要判断有多少子数组的和为sum-k,这样两个子数组相减的结果就可以累加到最终的结果中

核心就是一旦当前元素的累加和为sum，前面存在子数组相加的和为sum-k，那么中间的差距就形成了和为k的子数组

为了能够找到有多少个子数组能够形成和为sum的情况，需要使用一个map来记录

执行流程

  1. 定义一个unordered_map来记录多少个子数组可以形成和为sum的情况
  2. 当当前和为sum，并且之前存在和为sum-k的数组，那么就有了合法的子数组
  3. 当前的和sum记录一下，后面如果有sum+k的子数组出现，中间的差值又可以形成和为k的子数组
  4. 返回最后的结果

代码

根据以上分析，得出以下代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    //可以尝试滑动窗口
    int subarraySum(vector<int>& nums, int k) {
        //暴力法,会超时
        //从每个数出发，从而找出所有的和为k的组合
        int res=0;
        unordered_map<int,int> umap;
        //需要初始化，这样当sum等于k时也可以计算出结果
        umap[0]=1;
        int sum=0;
        for(int i=0;i<nums.size();++i){
            sum+=nums[i];
            //存在和为sum-k的子数组
            if(umap.find(sum-k)!=umap.end()){
                res+=umap[sum-k];
            }
            umap[sum]++;
        }
        return res;
    }
};

总结

直接从每一个元素出发进行累加的方法可行，但是会超时

利用前缀和的思路。当两个范围的差为k，说明中间形成了和为k的子数组，此时统计这些子数组，这样一次遍历就可以得到左右的结果，因为累加总是从前到后，并且只要两个点之间的差值为k，不论正负都可以得到最终正确的结果

可以自己找一个数组手动模拟