560. 和为 K 的子数组前缀和的运用

Bertha 。 2023-02-08 12:48 139阅读 0赞

链接：https://leetcode-cn.com/problems/subarray-sum-equals-k

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

示例 1：

输入：nums = [1,1,1], k = 2
    输出：2

示例 2：

输入：nums = [1,2,3], k = 3
    输出：2

示例 3：

输入：nums = [1,0,1], k = 1
    输出：4

提示：

1 <= nums.length <= 2 \* 10^4  
\-1000 <= nums\[i\] <= 1000  
\-10 ^ 7 <= k <= 10^7

## 题目分析 ##

这就是一道典型的，前缀和思想的题目。如果用前缀和思想解题，那么和为k的连续子数组的个数，就是先计算前缀和数组 arr，然后从中取出，差值为 k 的元素组合。

但是先把差分思想、前缀和思想放一放，看一看，用保底的暴力法，怎么解。

class Solution {
        
        public int subarraySum(int[] nums, int k) {
        
            int sum = 0;
            int count = 0;
            for (int i = 0 ; i< nums.length; i++) {
        
            	// 对于每个数nums[i]，遍历身后的子序列，和等于k时，count++
                for (int j = i; j< nums.length; j++) {
        
                    sum += nums[j];
                    if (sum == k) {
        
                        count++;
                    }
                }
                sum = 0; // 清空，再进入下一轮循环
            }
            return count;
        }
    }

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

n 平方的时间复杂度，一般都有优化空间。

怎么优化？前缀和

把 nums 看成一个差分数组，对它遍历，求前缀和数组 （[1109. 航班预订统计 差分思想的运用][1109. _]）

但是，前缀和结果 preSum，不要用数组存了，改用 HashMap，提高后续的访问效率。

因此，定义一个map，key 为前缀和，value 为前缀和的个数

在这个 map 中，map.get(preSum - k) 的值，就是和为 k 的子数组的个数

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAa2tra2s3MjEw_size_20_color_FFFFFF_t_70_g_se_x_16]  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAa2tra2s3MjEw_size_20_color_FFFFFF_t_70_g_se_x_16 1]

class Solution {
        
        public int subarraySum(int[] nums, int k) {
        
            int preSum = 0;
            int count = 0;
            // 1 定义map，保存和的个数
            HashMap<Integer, Integer> map = new HashMap<>();
            // 很有必要的初始化，若preSum刚好等于k时，
            // preSum - k = 0，和为k的子序列个数加一
            map.put(0,1); 
            
            for (int i = 0; i < nums.length; i++) {
        
                // 2.1 计算前缀和
                preSum += nums[i];
    
                if (map.containsKey(preSum - k)) {
        
                    // 3 前缀和为k的子序列的个数 ，累加
                    count += map.get(preSum - k);
                }
    
                // 2.2 前缀和为preSum的子序列的个数
                map.put(preSum, map.getOrDefault(preSum,0) + 1);
            }
            return count;
        }
    }

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAa2tra2s3MjEw_size_20_color_FFFFFF_t_70_g_se_x_16 2]  
暴力求解：1426 ms  
哈希 + 前缀和 ： 20ms

[1109. _]: https://editor.csdn.net/md/?articleId=122762324
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAa2tra2s3MjEw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20230208/ce0aa7ffabe8450b9f50a244722eea23.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAa2tra2s3MjEw_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20230208/b22fc0ac769f4f0385f999ce8ccb1e6d.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAa2tra2s3MjEw_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20230208/3ed82419591e4f0fa391abe96e2f137b.png