> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/hash/sum2index/maximum-size-subarray-sum-equals-k.md).

# 325. Maximum Size Subarray Sum Equals k

https\://leetcode.com/problems/maximum-size-subarray-sum-equals-k/description/

> Given an arraynumsand a target valuek, find the maximum length of a subarray that sums tok. If there isn't one, return 0 instead.
>
> **Note:**\
> The sum of the entirenumsarray is guaranteed to fit within the 32-bit signed integer range.
>
> **Example 1:**
>
> Givennums=`[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:**
>
> Givennums=`[-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?

## Thoughts

数组上和为k的子数组最长长度。找和为k的子数组，presum。

## Code

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

```java
 class Solution {
    public int maxSubArrayLen(int[] nums, int k) {
        Map<Integer, Integer> pos = new HashMap<>();
        int preSum = 0, maxLen = 0;
        pos.put(0, 0);
        for (int i = 0; i < nums.length; i++) {
            preSum += nums[i];
            if (pos.containsKey(preSum - k)) {
                maxLen = Math.max(maxLen, i + 1 - pos.get(preSum - k));
            }

            if (!pos.containsKey(preSum)) {
                pos.put(preSum, i + 1);
            }
        }
        return maxLen;
    }
}
```

## Analysis

做题耗时: 19 min Errors: 1. 还考虑了 pos.containsKey(preSum + k), 对应着sum(i, j) == -k , 不用考虑.

时间O(n), 空间O(n)