### 题目

Given an array nums and a target value k, find the maximum length of a subarray that sums to k. If there isn’t one, return 0 instead.

Note: The sum of the entire nums array is guaranteed to fit within the 32-bit signed integer range.

Example 1:

Given nums = [1, -1, 5, -2, 3], k = 3,
return 4. (because the subarray [1, -1, 5, -2] sums to 3 and is the longest)


Example 2:

Given nums = [-2, -1, 2, 1], k = 1,
return 2. (because the subarray [-1, 2] sums to 1 and is the longest)


Follow Up: Can you do it in O(n) time?

### 直观 $O(n^2)$ 的遍历数组

原数组：[1, -1, 5, -2, 3]



#### 代码

class Solution {
public int maxSubArrayLen(int[] nums, int k) {
int[] sums = new int[nums.length+1];
for (int i = 1; i < sums.length; i++) {
sums[i] = sums[i-1] + nums[i-1];
}
for (int i = nums.length; i > 0; i--) {
for (int j = 1, l = j + i - 1; l < sums.length; j++, l++) {
if (sums[l] - sums[j-1] == k) { return i; }
}
}
return 0;
}
}


### 用一个HashMap

       j         i    <- (if sum[i] - sum[j] = k)
|         |
[x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x]
|sum = k|


#### 代码

class Solution {
public int maxSubArrayLen(int[] nums, int k) {
Map<Integer,Integer> map = new HashMap<>();
int sum = 0, max = 0;
for (int i = 1; i <= nums.length; i++) {
sum += nums[i-1];
if (sum == k) {
max = Math.max(max,i);
} else if (map.containsKey(sum - k)) {
max = Math.max(max,i - map.get(sum - k));
}
if (!map.containsKey(sum)) { map.put(sum,i); } // 只保留和为某值的最短长度
}
return max;
}
}