链接：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的连续子数组的个数，就是求前缀和数组，然后从中取出，值为 k 、差值为 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. 航班预订统计 差分思想的运用）

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

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

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

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;}
}

暴力求解：1426 ms
哈希 + 前缀和 ： 20ms