325. Maximum Size Subarray Sum Equals k
Description
Given an integer array nums
and an integer k
, return the maximum length of a subarray that sums to k
. If there isn't 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
Tags
Hash Table
Solution
This is a prefix-sum problem, combining LeetCode 560. Subarray Sum Equals K and 525. Contiguous Array. Note that we only record the map from prefix-sum to its index when such prefix-sum does not exist in the map, since we need the longest subarray.
Complexity
Time complexity:
Space complexity:
Code
func maxSubArrayLen(nums []int, k int) int {
ans, preSum, sum2idx := 0, 0, map[int]int{0: -1}
for i, num := range nums {
preSum += num
if preIdx, ok := sum2idx[preSum-k]; ok {
if ans < i-preIdx {
ans = i - preIdx
}
}
if _, ok := sum2idx[preSum]; !ok {
sum2idx[preSum] = i
}
}
return ans
}
Last updated
Was this helpful?