Maximum Size Subarray Sum Equals k
Amazon
VisaThe problem
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.
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.
Input: nums = [-2,-1,2,1], k = 1 Output: 2 Explanation: The subarray [-1, 2] sums to 1 and is the longest.
Input: nums = [1,-5,1,5,1], k = 1
- 1 <= nums.length <= 2 * 105
- -104 <= nums[i] <= 104
- -109 <= k <= 109
cpp
class Solution {
public:
int maxSubArrayLen(vector<int>& nums, int k) {
// Your code goes herer
}
};java
class Solution {
public int maxSubArrayLen(int[] nums, int k) {
// Your code goes here
}
}python
class Solution(object):
def maxSubArrayLen(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
# Your code goes herejavascript
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var maxSubArrayLen = function(nums, k) {
// Your code goes here
};csharp
public class Solution
{
public int MaxSubArrayLen(int[] nums, int k)
{
// Your code goes here
}
}go
func maxSubArrayLen(nums []int, k int) int {
// Your code goes here
}Stuck? Show a way to structure it+
- 01Maintain the running prefix sum.
- 02Store the first index for every prefix value.
- 03For sum s, look for s-k.
- 04Use the earliest stored index to maximize length.
- 05Seed prefix zero at index minus one.
Reference answer
Then expect these follow-ups
How would you count all target-sum subarrays?
Tests: frequency maps
How do you return the actual boundaries?
Tests: index tracking
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question