# 325. Maximum Size Subarray Sum Equals k 和等于 k 的最长子数组长度

@TOC

## # 题目描述

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:

``````Input: nums = [1, -1, 5, -2, 3], k = 3
Output: 4
Explanation: The subarray [1, -1, 5, -2] sums to 3 and is the longest.
``````

Example 2:

``````Input: nums = [-2, -1, 2, 1], k = 1
Output: 2
Explanation: The subarray [-1, 2] sums to 1 and is the longest.
``````

• Can you do it in O(n) time?

## # 解题方法

### # prefix Sum

C++代码如下：

``````class Solution {
public:
int maxSubArrayLen(vector<int>& nums, int k) {
const int N = nums.size();
vector<int> preSum(N + 1, 0);
unordered_map<int, int> m;
m[0] = -1;
int res = 0;
for (int i = 0; i < N; ++i) {
preSum[i + 1] += preSum[i] + nums[i];
if (!m.count(preSum[i + 1])) {
m[preSum[i + 1]] = i;
}
int cur = preSum[i + 1] - k;
if (m.count(cur)) {
res = max(res, i - m[cur]);
}
}
return res;
}
};
``````

## # 日期

2019 年 9 月 22 日 —— 熬夜废掉半条命