LeetCode Solutions
325. Maximum Size Subarray Sum Equals k
Time: $O(n)$ Space: $O(n)$
class Solution {
public:
int maxSubArrayLen(vector<int>& nums, int k) {
int ans = 0;
int prefix = 0;
unordered_map<int, int> prefixToIndex{{0, -1}};
for (int i = 0; i < nums.size(); ++i) {
prefix += nums[i];
const int target = prefix - k;
if (prefixToIndex.count(target))
ans = max(ans, i - prefixToIndex[target]);
if (!prefixToIndex.count(prefix))
prefixToIndex[prefix] = i;
}
return ans;
}
};
class Solution {
public int maxSubArrayLen(int[] nums, int k) {
int ans = 0;
int prefix = 0;
Map<Integer, Integer> prefixToIndex = new HashMap<>();
prefixToIndex.put(0, -1);
for (int i = 0; i < nums.length; ++i) {
prefix += nums[i];
final int target = prefix - k;
if (prefixToIndex.containsKey(target))
ans = Math.max(ans, i - prefixToIndex.get(target));
prefixToIndex.putIfAbsent(prefix, i);
}
return ans;
}
}
class Solution:
def maxSubArrayLen(self, nums: List[int], k: int) -> int:
ans = 0
prefix = 0
prefixToIndex = {0: -1}
for i, num in enumerate(nums):
prefix += num
target = prefix - k
if target in prefixToIndex:
ans = max(ans, i - prefixToIndex[target])
if prefix not in prefixToIndex:
prefixToIndex[prefix] = i
return ans