560. Subarray Sum Equals K

Problem:

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:

1. The length of the array is in range [1, 20,000].
2. The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].

Analysis:
3/4/2018 update
If current sum is already in the preSum. We just need to add the occurrence by 1. If there is a sum that minus current sum equals to k later, so that we can have accurate number of subarrays.
------------------------------------------------------------------------------------------------------------------------------------

After finishing Path Sum III's preSum solution. This problem becomes super easy that I can one pass AC.

Solution:

class Solution {
    public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> preSum = new HashMap<>();
        int res = 0,  sum = 0;
        preSum.put(0, 1);
        for (int n: nums) {
            sum += n;
            int diff = sum - k;
            res += preSum.getOrDefault(diff, 0);
            preSum.put(sum, preSum.getOrDefault(sum, 0) + 1);
        }
        return res;
    }
}