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(n2)。使用双循环枚举了所有的子数组，所以时间复杂度为O(n2)。
空间复杂度：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%， 这个时间消耗小相较于思路一小了很多