力扣Leetcode第560题：和为k的子数组（前缀和及其优化）

Myth丶恋晨 2023-02-13 03:51 15阅读 0赞

题目描述：

> 给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。
> 
> 示例 1 :
> 
> 输入:nums = \[1,1,1\], k = 2  
> 输出: 2 , \[1,1\] 与 \[1,1\] 为两种不同的情况
> 
> 说明 : 数组的长度为 \[1, 20,000\]。 数组中元素的范围是 \[-1000, 1000\] ，且整数 k 的范围是 \[-1e7,1e7\]

题目很容易理解,类似于从所有的排列组合里面,找到符合要求的部分.

### 一.暴力穷举 ###

暴力法是非常容易想到的,　由于子数组是连续的，只要双重循环，就可以组合出所有的子数组，然后在此基础上去判断是否满足条件，统计数量即可．

class Solution {
        
        public int subarraySum(int[] nums, int k) {
        
            int count=0;
            for(int i=0;i<nums.length;i++){
        
                int res=k-nums[i];//用减法代替加和判断
                if(res==0){
        
                    count++;
                }
                //满足条件之后不能退出循环,要继续向后遍历
                for(int j=i+1;j<nums.length;j++){
        
                    res=res-nums[j];
                    if(res==0){
        
                        count++;
                    }
                }
            }
            return count;
        }
    }

这种方法的时间复杂度显然是O(n2).

### 二.前缀和 ###

在前面的暴力计算过程中可以看出来，到某一个位置ｊ的时候，计算的是从ｉ位置到ｊ的的所有加和。（虽然写法将加法换成了减法，但是一样是判断了和是否为ｋ）  
然而暴力法从每一个位置都要循环所有，然后逐渐相加。

想一想，如果我们先循环一遍引入前缀和数组，也就是把每个位置的前缀和都算出来．这样某一截子数组的和就可以用两个位置的前缀和进行减法计算，得出结果。

这个过程我们以数组：［３，７，４，２］和目标值Ｋ＝７为例．  
可以算出前缀和数组为：  
,.![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA5Mjc4Nw_size_16_color_FFFFFF_t_70]  
有了前缀和数组之后，接着遍历计算差值：

*  从0开始，后面7-0=7，这是一个满足条件的子数组，代表的是原数组的子数组\[3 4\]，再往后没有了；
 *  从3开始，没有；
 *  从7开始，14-7=7，代表==\[7\]==这个子数组；
 *  从14开始，没有；
 *  从16开始，也没有。

因此结果是2.

直接看来时间复杂度和暴力法一样，而且还用了额外的数组（这种方法的二重循环里面总共进行一次判断操作，而暴力法是两次，但是实际应该没有影响吧）。

代码如下：

public class Solution {
        
        public int subarraySum(int[] nums, int k) {
        
            int len = nums.length;
    
            // 计算前缀和数组
            int[] preSum = new int[len + 1];
            preSum[0] = 0;
            for (int i=0; i<len; i++) {
        
                preSum[i+1] = preSum[i] + nums[i];
            }
    
            int count = 0;
            for (int left=0; left<len; left++) {
        
                for (int right=left; right<len; right++) {
        
                    // 计算[left..right]中间的区间和，注意下标偏移
                    if (preSum[right + 1] - preSum[left] == k) {
        
                        count++;
                    }
                }
            }
            return count;
        }
    }

从在leetcode的提交记录看,这种方法确实比暴力法还要慢一些

### 三．前缀和＋利用哈希表进行优化 ###

第二种方法里我们已经用了前缀和，但对前缀和数组进行计算和存储之后，仍然是需要再双重遍历进行计算的。

这时候来想一想我们计算结果的方式：

任意两个前缀和 preSum\[ j \] 和 preSum\[ i \] 表示i到j之间的子数组的和，和为 k 说明满足条件, 就让 count+1 . 那和为 k 的 preSum 是不是本身就会重复 ? 和为别的值的 preSum 也会重复.  
如果我们把这些都统计起来，那么一次就能直接把相同情况的进行累加，而不用遍历去重新统计了。

我们知道，java里的集合map的特点是键值对的key不重复，因此我们利用map，在计算前缀和的同时就不断更新这个map。

比如还是3 4 7 2这个nums数组。我们模拟一下执行过程：

1.开始预放入一个<0,1>对，代表前缀和为0的子数组有1个。  
2.遍历到3，计算当前位置的preSum，是3，同时我们查看当前的map里，有没有满足key是preSum-k的键值对。由于前面没有3-7=-3为value的对，所以不做操作。  
接着更新这个map，要维护的是map的性质，把当前的preSum加进去，key是3，value是多少呢，因为本身没有，所以+1.放入<3,1>

> 为什么是preSum-k呢？  
> 我们知道从　i　位置的preSum\[i\]到j位置的preSum\[j\]，preSum\[j\]-preSum\[i\]=k,说明i到j这个子数组是满足条件的。  
> 对上面的等式进行移项，得到当前　j　位置的preSum\[j\]-k=preSum\[i\]，也就是说，找到了preSum\[i\]，就是满足条件的。  
> 那既然已经用map进行了存储，我们只要看在map里有没有preSum\[i\]，有的话就加上去，并且直接加上有的个数。

3.遍历到4，计算当前位置preSum是7，查看map里面有没有7-7=0？有，所以count要加上0对应的value：1，（事实上是子数组\[3,4\]）。  
接着更新map，这里preSum是7，之前没有7这个key，所以放入<7,1>

4.遍历到7，计算当前位置preSum是14，查看map里有没有14-7=7？有，所以count加上7对应的value是1，（事实上是子数组：\[7\]）。  
接着更新map，preSum是14，之前没有14，所以放入<14,1>

5.遍历到2，计算当前位置preSum是16，没有16-7=9？，没有，所以不操作。

6.接着更新map，之前没有16，所以放入<16,1>  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA5Mjc4Nw_size_16_color_FFFFFF_t_70 1][]  
一开始我自己有疑问，每次count加的是value，而不是+1。如果前面这个位置被访问了多次，每次都是+value，是不是会重复计算了呢？  
事实上不会，这种“重复计算”正好代表了计算子数组的完整性。这里是类似排列组合的感觉：

**直观一点来看，比如数组是0 0 ，k=0。  
1.开始map放入<0,1>，  
2.遍历到第一个0，存在0-0=0的key，count加上对应的value=0+1=1；更新map，之前已经有了key为0的键值对，所以map更新为<0,2>；  
3.遍历到第二个0，存在0-0=0的key，count加上对应的value=1+2=3；更新map，之前已经有了key为0的键值对，放入<0,3>；  
可以看到，第二次直接在1的基础上加了2，得到了3.这多算了吗？没有，正好count=3才是正确答案。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA5Mjc4Nw_size_16_color_FFFFFF_t_70 2]  
也就是说，当前位置的前缀和，重复了之前某个位置的前缀和，那么**之前的那些满足条件的每一个位置，持续到当前位置，都会是一个符合要求的子数组。**

代码：

public class Solution {
        
        public int subarraySum(int[] nums, int k) {
        
            // key：前缀和，value：key 对应的前缀和的个数
            Map<Integer, Integer> map = new HashMap<>();
            // 对于下标为 0 的元素，前缀和为 0，个数为 1
            map.put(0, 1);
    
            int preSum = 0;
            int count = 0;
            for (int num : nums) {
        
                preSum += num;
    
                // 先获得前缀和为 preSum - k 的个数，加到计数变量里
                if (map.containsKey(preSum - k)) {
        
                    count += map.get(preSum - k);
                }
    
                // 然后维护这个 map 的定义
                map.put(preSum, map.getOrDefault(preSum, 0) + 1);
            }
            return count;
        }
    }

其中：map的getOrDefault方法，参数是如果有preSum这个key，那就是得到对应的value，如果没有就得到指定的0值。

仔细看一看代码，这里面containsKey方法的使用，如果让我们自己实现，肯定也是会进行遍历查找的，因此做法比较容易理解，仍然是在双重循环查找，只不过利用了map的方法优化了解答。

上面代码后几行也可以换一种方式写：

for (int num : nums) {
        
        preSum += num;
        // 先获得前缀和为 preSum - k 的个数，加到计数变量里
        int preCount=map.getOrDefault(preSum-k,0);
        count+=preCount;
        // 然后维护 map 的定义            map.put(preSum,preCount+1);
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA5Mjc4Nw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200527120107525.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA5Mjc4Nw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA5Mjc4Nw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200527122905607.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA5Mjc4Nw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA5Mjc4Nw_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200527123635384.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA5Mjc4Nw==,size_16,color_FFFFFF,t_70