325

325. Maximum Size Subarray Sum Equals k (Medium)

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

Companies:
Facebook, Microsoft, Goldman Sachs

Related Topics:
Array, Hash Table

Similar Questions:

• Minimum Size Subarray Sum (Medium)
• Range Sum Query - Immutable (Easy)
• Contiguous Array (Medium)
• Subarray Product Less Than K (Medium)

Solution 1. Prefix State Map

// OJ: https://leetcode.com/problems/maximum-size-subarray-sum-equals-k/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
public:
    int maxSubArrayLen(vector<int>& A, int k) {
        unordered_map<int, int> m{{0,-1}}; // prefix sum -> first index
        int ans = 0;
        for (int i = 0, sum = 0; i < A.size(); ++i) {
            sum += A[i];
            int target = sum - k;
            if (m.count(target)) ans = max(ans, i - m[target]);
            if (m.count(sum) == 0) m[sum] = i;
        }
        return ans;
    }
};