和为 K 的子数组

题目链接

和为 K 的子数组

题目描述

注意点

• -1000 <= nums[i] <= 1000
• 子数组是数组中元素的连续非空序列

解答思路

• 最初想到的思路是使用递归，遍历整个数组，当访问到idx位置处的元素时，可以根据idx - 1作为末尾元素的子数组和推出idx作为末尾元素的子数组和（也就是nums[idx]再加上list.foreach(idx - 1) + nums[idx]），这样连续写入新的List集合非常耗时，效率不如暴力解法，最终超出时间限制，需要找到更加巧妙的方法
• 发现本题和路径总和|||相似，且更简单，可将其看作只有左子树或右子树的情况，利用前缀和+哈希表解决本题
• 前缀和的思想是：从头开始遍历整个数组，不断更新从第1个元素开始到第i个元素的前缀和currSum及所有的前缀和映射表map，此时寻找将第i个元素作为末尾元素时满足条件的子数组，且现在的实际目标值为currSum - k，需要从（0，i - 1）找到和为currSum - k的前缀和组合，也就是从map中找到前缀和为currSum - k对应的数量，例子如下：
• 对于{3，4，5，-1，1，7，2}，k = 7，当遍历到第五个元素7
  • 此时currSum = 21
  • 递归推出的map为{(0, 1), (3, 1), (7, 1), (12, 2), (11, 1), (19, 1)}
  • 实际目标值为currSum - k = 12
  • currSum - k对应map中key为12的值为2，有两个组合满足题意以第五个元素作为末尾元素时和为k的子数组为{-1, 1, 7}和{7}

代码

public class Solution {
    public int subarraySum(int[] nums, int k) {
        int res = 0;
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        int currSum = 0;
        for (int i = 0; i < nums.length; i++) {
            currSum += nums[i];
            int diffSum = currSum - k;
            res += map.getOrDefault(diffSum, 0);
            map.put(currSum, map.getOrDefault(currSum, 0) + 1);
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

关键点

• 前缀和的思想