Medium
跟之前做的一道two sum data structure design蛮像
We know the key to solve this problem is SUM[i, j]. So if we know SUM[0, i - 1] and SUM[0, j], then we can easily get SUM[i, j]. To achieve this, we just need to go through the array, calculate the current sum and save number of all seen PreSum to a HashMap. Time complexity O(n), Space complexity O(n).

class Solution {
    //< O(N^2)
    public int subarraySum(int[] nums, int k) {
        int count = 0;
        int sum = 0;
        Map<Integer, Integer> preSum = new HashMap<>();
        preSum.put(0, 1);
        //we want to know how many subarray exists such that s[i,j] == k
        //s[i, j] = s[0, j] - s[0, i- 1]
        //k = sum - s[0, i - 1]
        for (int i = 0; i < nums.length; i++){
            sum += nums[i];
            count += preSum.getOrDefault(sum - k, 0);
            preSum.put(sum, preSum.getOrDefault(sum, 0) + 1);
        }
        return count;
    }
}