325. Maximum Size Subarray Sum Equals k
https://leetcode.com/problems/maximum-size-subarray-sum-equals-k
https://www.lintcode.com/problem/maximum-size-subarray-sum-equals-k/description
https://www.lintcode.com/problem/maximum-size-subarray-sum-equals-k/description
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.
The sum of the entire nums array is guaranteed to fit within the 32-bit signed integer range.
Example 1:
Input: nums =[1, -1, 5, -2, 3], k =3Output: 4 Explanation: The subarray[1, -1, 5, -2]sums to 3 and is the longest.
Example 2:
Input: nums =[-2, -1, 2, 1], k =1Output: 2 Explanation: The subarray[-1, 2]sums to 1 and is the longest.
Follow Up:
Can you do it in O(n) time?
Can you do it in O(n) time?
----
Intuition
Sub array sum => preprocess input to get range sum in const time => create prefix sum
Sum from i to j = prefix[j] - prefix[i - 1], length of subarray = j - 1
Problem reduces to Max (j - i) such that prefix[j] - prefix[i] = k
Instead of brute force, we can lookup complement prefix[index] - k from hash map
Hash Map < Prefix Sum, Index>
Seed with sum = 0, index = -1
Also save the current prefix sum and index as we traverse L to R
Only save first index, do not overwrite since we need longest subarray
---
Time - O(N)
Space - O(N)
---
Related problems
560-subarray-sum-equals-k
---
Intuition
Sub array sum => preprocess input to get range sum in const time => create prefix sum
Sum from i to j = prefix[j] - prefix[i - 1], length of subarray = j - 1
Problem reduces to Max (j - i) such that prefix[j] - prefix[i] = k
Instead of brute force, we can lookup complement prefix[index] - k from hash map
Hash Map < Prefix Sum, Index>
Seed with sum = 0, index = -1
Also save the current prefix sum and index as we traverse L to R
Only save first index, do not overwrite since we need longest subarray
---
Time - O(N)
Space - O(N)
---
Related problems
560-subarray-sum-equals-k
---
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| public class Solution { | |
| /** | |
| * @param nums: an array | |
| * @param k: a target value | |
| * @return: the maximum length of a subarray that sums to k | |
| */ | |
| public int maxSubArrayLen(int[] nums, int k) { | |
| Map<Integer, Integer> map = new HashMap<Integer, Integer>(); | |
| // cumulative sum | |
| int sum = 0; | |
| int ans = 0; | |
| for (int i = 0; i < nums.length; i++) { | |
| sum += nums[i]; | |
| if (sum == k) { | |
| // max possible length .. cumulative sum from start of array | |
| ans = i + 1; | |
| } else if (map.containsKey(sum - k)) { | |
| // length of array between sum, and complement | |
| ans = Math.max(ans, i - map.get(sum - k)); | |
| } | |
| // preserve the left most index, do not overwrite if sum appears again | |
| if (!map.containsKey(sum)) { | |
| map.put(sum, i); | |
| } | |
| } | |
| return ans; | |
| } | |
| } |
