[LeetCode] 325. Maximum Size Subarray Sum Equals k 和等于k的最长子数组

2021年09月15日 阅读数：1

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.html

Example 1:java

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)python

Example 2:数组

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

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

Java:blog

```public int maxSubArrayLen(int[] nums, int k) {
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
int max = 0;
int sum=0;
for(int i=0; i<nums.length; i++){
sum += nums[i];

if(sum==k){
max = Math.max(max, i+1);
}

int diff = sum-k;

if(map.containsKey(diff)){
max = Math.max(max, i-map.get(diff));
}

if(!map.containsKey(sum)){
map.put(sum, i);
}
}

return max;
}　　```

Python: Time:  O(n)， Space: O(n)

```class Solution(object):
def maxSubArrayLen(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
sums = {}
cur_sum, max_len = 0, 0
for i in xrange(len(nums)):
cur_sum += nums[i]
if cur_sum == k:
max_len = i + 1
elif cur_sum - k in sums:
max_len = max(max_len, i - sums[cur_sum - k])
if cur_sum not in sums:
sums[cur_sum] = i  # Only keep the smallest index.
return max_len　```

Python: wo

```class Solution():
def maxSubarry(self, nums, k):
m = {0: -1}
sm = 0
for i in range(len(nums)):
sm += nums[i]
if sm not in m:
m[sm] = i
if sm - k in m:
max_len = max(max_len, i - m[sm-k])

return max_len　　```

C++:

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

[LeetCode] 53. Maximum Subarray 最大子数组

[LeetCode] 209. Minimum Size Subarray Sum 最短子数组之和

[LeetCode] 560. Subarray Sum Equals K 子数组和为K

Range Sum Query - Immutable