Medium
一刷的筆記是直接復制粘貼過來的別人的語言，果然就完全沒印象。雖然看似快，其實這樣是最事倍功半的。一定要懂了，用自己的語言簡單總結一下就好。別直接copy，沒有意思。

第一種解法是O(N2)的brute force,就不寫了。第二種方法是O(N)利用sum[i, j] = sum[0, j] - sum[0, i-1] where sum[i,j] stands for sum for substring[i,j] inclusively. 利用preSum這個裝著preSum和它的頻次的map, 遍歷是一邊加sum以便存入preSum.一般檢查有沒有之前的presum = sum - k的，為什么是sum - k的呢？因為preSum[0,i] + subarraySum = preSum[0, j], 知道 subarraySum = k, preSum[0, j] = sum, 所以要找有沒有preSum[0,i] = sum - k的。能找到幾個這樣的preSum, 就能找到幾個與之對應的subarray， 所以res++.

class Solution {
    public int subarraySum(int[] nums, int k) {
        if (nums == null || nums.length == 0){
            return 0;
        }
        int res = 0;
        int sum = 0;
        Map<Integer, Integer> preSum = new HashMap<>();
        preSum.put(0, 1);
        for (int i = 0; i < nums.length; i++){
            sum += nums[i];
            if (preSum.containsKey(sum - k)){
                res += preSum.get(sum - k);    
            }
            preSum.put(sum, preSum.getOrDefault(sum, 0) + 1);
        }
        return res;
    }
}