Back

325. Maximum Size Subarray Sum Equals k

Medium
Array
Hash Table
Prefix Sum
Solve on LeetCode View Solutions

Description

From doocs/leetcode

Given an integer array nums and an integer k, return the maximum length of a subarray that sums to k. If there is not 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

Hints

Hint 1
Compute the prefix sum array where psum[i] is the sum of all the elements from <i>0</i> to <i>i</i>.
Hint 2
At each index <i>i</i>, the sum of the prefix is psum[i], so we are searching for the index x where psum[x] = psum[i] - k. The subarray [x + 1, i] will be of sum k.
Hint 3
Use a hashmap to get the index x efficiently or to determine that it does not exist.

Similar Questions

Minimum Size Subarray Sum
Medium
Range Sum Query - Immutable
Easy
Contiguous Array
Medium
Subarray Product Less Than K
Medium
Maximum Beauty of an Array After Applying Operation
Medium
Shortest Subarray With OR at Least K II
Medium

Statistics

Acceptance
50.8%
Submissions
429,904
Accepted
218,222