Question

325. Maximum Size Subarray Sum Equals k

中文文档

Description

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

Solutions

Solution 1

class Solution:
  def maxSubArrayLen(self, nums: List[int], k: int) -> int:
    d = {0: -1}
    ans = s = 0
    for i, x in enumerate(nums):
      s += x
      if s - k in d:
        ans = max(ans, i - d[s - k])
      if s not in d:
        d[s] = i
    return ans

class Solution {
  public int maxSubArrayLen(int[] nums, int k) {
    Map<Long, Integer> d = new HashMap<>();
    d.put(0L, -1);
    int ans = 0;
    long s = 0;
    for (int i = 0; i < nums.length; ++i) {
      s += nums[i];
      ans = Math.max(ans, i - d.getOrDefault(s - k, i));
      d.putIfAbsent(s, i);
    }
    return ans;
  }
}

class Solution {
public:
  int maxSubArrayLen(vector<int>& nums, int k) {
    unordered_map<long long, int> d{{0, -1}};
    int ans = 0;
    long long s = 0;
    for (int i = 0; i < nums.size(); ++i) {
      s += nums[i];
      if (d.count(s - k)) {
        ans = max(ans, i - d[s - k]);
      }
      if (!d.count(s)) {
        d[s] = i;
      }
    }
    return ans;
  }
};

func maxSubArrayLen(nums []int, k int) (ans int) {
  d := map[int]int{0: -1}
  s := 0
  for i, x := range nums {
    s += x
    if j, ok := d[s-k]; ok && ans < i-j {
      ans = i - j
    }
    if _, ok := d[s]; !ok {
      d[s] = i
    }
  }
  return
}

function maxSubArrayLen(nums: number[], k: number): number {
  const d: Map<number, number> = new Map();
  d.set(0, -1);
  let ans = 0;
  let s = 0;
  for (let i = 0; i < nums.length; ++i) {
    s += nums[i];
    if (d.has(s - k)) {
      ans = Math.max(ans, i - d.get(s - k)!);
    }
    if (!d.has(s)) {
      d.set(s, i);
    }
  }
  return ans;
}