Welcome to Subscribe On Youtube

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

• Java
• C++
• Python
• Go
• TypeScript

• 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;
      }
  };
  

• 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
  
  

• 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;
  }
  
  

All Problems

All Solutions