325. Maximum Size Subarray Sum Equals k
- Total Accepted: 13137
- Total Submissions: 31728
- Difficulty: Medium
- Contributors: Admin
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:
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)
Example 2:
Given nums = [-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?
Code
class Solution(object):
def maxSubArrayLen(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
sum = 0
max_res = 0
# key: sum of all elements so far, value: the index so far
sum_map = dict()
for i, n in enumerate(nums):
sum += n
if sum == k:
max_res = i + 1
elif sum_map.get(sum-k, None) is not None:
max_res = max(max_res, i - sum_map[sum-k])
# if sum already exists in sum_map, its index should be
# smaller than the current index. Since we want to find
# the maximum length of subarray, the smaller index
# should be kept.
if sum_map.get(sum, None) is None:
sum_map[sum] = i
return max_res
Idea
The obvious brute-force way is to have two pointers, i and j (0 <=i<len(nums), i+1<=j <len(nums)), and test whether nums[i:j+1] sum to k. This takes O(n^2) time where n is the length of nums.
Our code uses the following idea: Create a dictionary sum_map which records the sum of all previous elements when traversing nums. Its key is the sum of all elements so far and its value is the current index.
During the traversal, we can check whether the current sum so far equals to k (line 15-16). We can also check whether sum_map contains sum-k as a key. If so, that means a subarray can be found between `sum_map[sum-k]` and `i`.
Reference: https://discuss.leetcode.com/topic/33259/o-n-super-clean-9-line-java-solution-with-hashmap