325. Maximum Size Subarray Sum Equals k#
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.
Example 1
Input: nums = [1, -1, 5, -2, 3], k = 3
Output: 4
Explanation: 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: subarray [-1, 2] sums to 1 and is the longest.
Approach 1: Using two loops#
1public class Solution {
2
3 public int maxSubArrayLen(int[] nums, int k) {
4 int maxLen = 0;
5 for (int i = 0; i < nums.length; ++i) {
6 int currentSum = 0;
7 for (int j = i; j < nums.length; ++j) {
8 currentSum += nums[j];
9
10 if (currentSum == k) {
11 maxLen = Math.max(maxLen, j - i + 1);
12 }
13 }
14 }
15 return maxLen;
16 }
17}
Approach 2: Using prefix sum in HashMap#
1public class Solution {
2
3 public int maxSubArrayLen(int[] nums, int k) {
4 Map<Integer, Integer> map = new HashMap<>();
5 map.put(0, -1);
6
7 int prefixSum = 0;
8 int maxLen = 0;
9
10 for (int i = 0; i < nums.length; ++i) {
11 prefixSum += nums[i];
12 if (map.containsKey(prefixSum - k)) {
13 maxLen = Math.max(maxLen, i - map.get(prefixSum - k));
14 }
15 map.putIfAbsent(prefixSum, i);
16 }
17
18 return maxLen;
19 }
20}