Description#
Given an integer array nums and an integer k, return the maximum length of a subarray that sums to k. If there is not one, return 0 instead.
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.
Constraints:
1 <= nums.length <= 2 * 105-104 <= nums[i] <= 104-109 <= k <= 109
Solutions#
Solution 1#
1
2
3
4
5
6
7
8
9
10
11
| class Solution:
def maxSubArrayLen(self, nums: List[int], k: int) -> int:
d = {0: -1}
ans = s = 0
for i, x in enumerate(nums):
s += x
if s - k in d:
ans = max(ans, i - d[s - k])
if s not in d:
d[s] = i
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public int maxSubArrayLen(int[] nums, int k) {
Map<Long, Integer> d = new HashMap<>();
d.put(0L, -1);
int ans = 0;
long s = 0;
for (int i = 0; i < nums.length; ++i) {
s += nums[i];
ans = Math.max(ans, i - d.getOrDefault(s - k, i));
d.putIfAbsent(s, i);
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public:
int maxSubArrayLen(vector<int>& nums, int k) {
unordered_map<long long, int> d{{0, -1}};
int ans = 0;
long long s = 0;
for (int i = 0; i < nums.size(); ++i) {
s += nums[i];
if (d.count(s - k)) {
ans = max(ans, i - d[s - k]);
}
if (!d.count(s)) {
d[s] = i;
}
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| func maxSubArrayLen(nums []int, k int) (ans int) {
d := map[int]int{0: -1}
s := 0
for i, x := range nums {
s += x
if j, ok := d[s-k]; ok && ans < i-j {
ans = i - j
}
if _, ok := d[s]; !ok {
d[s] = i
}
}
return
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| function maxSubArrayLen(nums: number[], k: number): number {
const d: Map<number, number> = new Map();
d.set(0, -1);
let ans = 0;
let s = 0;
for (let i = 0; i < nums.length; ++i) {
s += nums[i];
if (d.has(s - k)) {
ans = Math.max(ans, i - d.get(s - k)!);
}
if (!d.has(s)) {
d.set(s, i);
}
}
return ans;
}
|
