leetcode hot 100-560. 和为K的子数组

560. 和为K的子数组

给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。

示例 1 :

输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况

说明 :

数组的长度为 [1, 20,000]。
数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。

思路一：暴力法

双重循环，枚举所有的子数组，判断每个子数组的和是否为k

 1 class Solution {
 2     public int subarraySum(int[] nums, int k) {
 3         // 双重循环
 4         // 枚举所有的子数组，判断每个子数组的和是否为k
 5         int count = 0;
 6         int len = nums.length;
 7         for(int i = 0; i < len; i++){
 8             int sum = 0;
 9             for(int j = i; j < len; j++){
10                 sum += nums[j];
11                 count += ((sum == k) ? 1 : 0);
12             }
13         }
14         return count;
15     }
16 }

leetcode 执行用时：1783 ms > 5.08%, 内存消耗：41.7 MB > 5.04%，从执行时间上看这个算法很低效

复杂度分析：

时间复杂度：O(n²)。使用双循环枚举了所有的子数组，所以时间复杂度为O(n²)。

空间复杂度：O(1)。只使用了常数个变量的空间。

思路二：前缀和 + 哈希

思路参考：https://leetcode-cn.com/problems/subarray-sum-equals-k/solution/he-wei-kde-zi-shu-zu-by-leetcode-solution/ 和 https://leetcode-cn.com/problems/subarray-sum-equals-k/solution/bao-li-jie-fa-qian-zhui-he-qian-zhui-he-you-hua-ja/

假设有一个前缀和数组，这个数组的每个元素preSum[i]存储了 nums[i] 元素和nums[i]元素之前的所有元素之和，即[0, i]之间的所有元素和，那么如果[i, j]之间的元素元素之和为恰好k, 那么

preSum[i] - preSum[j] = k

所以要判断是否存在以 nums[i] 结尾的子数组的和为 k , 只需要判断是否存在 preSum[j] 即可，对等式进行移项后得到

preSum[i] - k = preSum[j]

所以要判断是否存在以 nums[i] 结尾的子数组的和为 k , 只需要判断是否存在 (preSum[i] - k) 即可，所以如果我们创建一个HashMap, map中存储的键是前缀和、值是该前缀和出现的次数，那么当(preSum[i] - k) 存在于map中时，map.get(preSum[i] - k) 前缀和出现的次数即表示了以 nums[i] 结尾的子数组中和为 k的子数组的数量。让计数器加上这个出现次数即可。

【优化】因为因为preSum[i]的计算只和preSum[i-1]有关，所以可以不必提前把所有元素的前缀和求出来，不需要维护一个前缀和数组，只需要定义一个preSum然后不断更新迭代即可，可以在遍历数组的同时求出当前元素的前缀和

 1 class Solution {
 2     public int subarraySum(int[] nums, int k) {
 3 
 4         HashMap<Integer, Integer> map = new HashMap<>();
 5         map.put(0, 1);  // 当还没有枚举元素时，前缀和为0,出现了一次
 6         int preSum = 0;
 7         int count = 0;
 8         for(int num : nums){
 9             preSum += num;
10             if(map.containsKey(preSum - k)){
11                 count += map.get(preSum - k);
12             }
13             map.put(preSum, map.getOrDefault(preSum, 0) + 1);  // 把当前前缀和对应的值加一
14         }
15         return count;
16     }
17 }

leetcode 执行用时：26 ms > 49.73%, 内存消耗：40.9 MB > 15.84%，这个时间消耗小相较于思路一小了很多

复杂度分析：

时间复杂度：O(n)。遍历了一次数组，所以时间复杂度为O(n)。

空间复杂度：O(n)。空间开销主要来自map, map中的元素个数决定了空间复杂度，map中最多有n个键值对，即当所有元素均为正数或者均为负数时，所有前缀和都是一个键值对，此时空间复杂度为O(n)。