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;
}
}
