LeetCode【560】和为k的子数组

题目：

思路：
转化为前缀和问题，和为k，即为：前缀和差值为k的情况统计； 为什么要转化为前缀和呢？因为和为k的子数组可能有n个元素，但是前缀和差值为k，只有两个元素，可以借助map去做，类似两数之和问题。

代码：

    public int subarraySum(int[] nums, int k) {

        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);     // 这里注意加0，是为了如果第一个元素就为k，那需要直接计算出

        int preSum = 0;
        int count = 0;

        for (int num : nums) {
            preSum += num;

            if (map.get(preSum - k) != null) {
                count += map.get(preSum - k);
            }

            map.put(preSum, map.getOrDefault(preSum, 0) + 1);
        }

        return count;

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21