Medium
o(n2)的方法太过naive不写了，主要看O(n)的
写个式子会比较好理解为什么里面要找hash.containsKey(sum - k)
反正有道题是preSum之类的跟这个很类似

i < j
sum[0, j] = nums[0] + nums[1] + nums[2] + ... + nums[j]
sum[0, i] = nums[0] + nums[1] + nums[2] + ... + nums[i]
sum[i + 1, j] = sum[0, j] - sum[0, i]

在本题代码里，sum = sum[0, j]
我们要找的是所有使得sum[i ,j] == k中j - i + 1最大的情况(sum[0, j]也会被检查是不是等于k)
所以每当我们得到一个sum[0, j]的时候，我们先判断sum[0, j] == k or not. 如果等于，那很好，直接 j + 1就是长度；如果不等于，我们就要去找有没有那么一个 subarray的和等于k呢，也就是sum[i+1, j] == k. 那如果有的话，我们就应该早就有sum[0, i] == sum - k 在hashMap里面当作前缀和存起来了.

image.png

 class Solution {
    public int maxSubArrayLen(int[] nums, int k) {
        // [1,-1,5,-2,3]
        // k =        3
        // sum =      1   0   5   3   6
        // i =        0   1   2   3   4
        // sum - k = -2  -3   2   0   3
        // maxLen= 4 
        
        //hashMap: 
        //key: sum before index i inclusively
        //value : index i
        //[1, 0]
        //[0, 1]      
        //[5, 2]
        //[3, 3]      
        int sum = 0;
        int maxLen = 0;
        Map<Integer, Integer> hash = new HashMap<>();
        for (int i = 0; i < nums.length; i++){
            sum += nums[i];
            if (sum == k){
                maxLen = i + 1;
            } else if (hash.containsKey(sum - k)){
                maxLen = Math.max(maxLen, i - hash.get(sum - k));
            } 
            if (!hash.containsKey(sum)){
                hash.put(sum, i);
            }
        }
        // i < j
        // sum[i + 1, j] = k
        // sum[0,j] - sum[0,i]  = sum[i + 1, j]
        // sum   -   ?          = k
        return maxLen;
        
    }
}