Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.
Example 1:
Input:nums = [1,1,1], k = 2
Output: 2
Note:
- The length of the array is in range [1, 20,000].
- The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].
题目标签：Array, Map
题目给了我们一个nums array 和一个 k， 要我们找出有多少个子数组 之和是等于 k的。
一开始想到的是暴力解法，虽然能够通过，但是n*n 始终是太慢。
这题可以利用HashMap，把出现过的sum 当作key 存入， 把这个sum 出现过的次数 当作value 存入。
遍历nums array，一直更新sum，然后去map 里找有没有 sum - k，有的话说明 sum - k 是一个旧的sum，之前出现过。换句话说，新的sum - 旧的sum = k，说明 新的sum 减去 旧的sum，剩下的那一段的 和 等于k， 找到了一个子数组之和 = k的。然后在把新的sum 存入 map里。
这题的关键就是，当我们知道了一个 sum（0，i） 和 sum（0，j）的话，我们也就知道了 sum（i+1， j）。
所以当我们知道了目前所有旧的sum， 当我们有了一个新的sum，我们可以利用map 去找到 新的sum - k 是不是在map里存在。一旦存在，说明了我们找到了一个 子数组它的和为k。
要注意的是，这里count +的是map 里的value，而不是count++， 因为当你在map 里找到了一个 sum - k的旧sum的时候，这个旧的sum 可能出现过2次，换句话说，可能有两个长度不一样的子数组，但是它们的和都等于 sum - k（因为有负数）。所以这里要加上旧sum 的出现次数2，因为你找到了两个不同的子数组它们的和都为k。
Java Solution:
Runtime beats 67.25%
完成日期：10/03/2017
关键词：Array, HashMap
关键点：把所有出现过的sum存入map：sum为key，出现的次数为value；利用map来找k (新sum - k =? 任何旧sum)
class Solution
{
public int subarraySum(int[] nums, int k)
{
int count = 0;
int sum = 0; Map<Integer, Integer> map = new HashMap<>();
map.put(0, 1); // initial value sum = 0, occurrence = 1 for case sum = k, k - k = 0 counts for(int i=0; i<nums.length; i++) // iterate nums array
{
sum += nums[i]; // update sum if(map.containsKey(sum - k)) // if map has sum - k, meaning this new sum - old sum = k
count += map.get(sum - k); // previous sum might appear more than once
// this is why we need to add its value
map.put(sum, map.getOrDefault(sum, 0) + 1); // save new sum into map
} return count;
}
}
参考资料：
https://discuss.leetcode.com/topic/87850/java-solution-presum-hashmap
LeetCode 题目列表 - LeetCode Questions List