325. Maximum Size Subarray Sum Equals k

Problem Statement

link: LeetCode.cn 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:

Input: nums = [1,-1,5,-2,3], k = 3 Output: 3

Input: nums = [-2,-1,2,1], k = 1 Output: 2

Constraints: 1 <= nums.length <= 2 * 105 -104 <= nums[i] <= 104 -109 <= k <= 109

Solution Approach

The solution uses a hash table to track prefix sums and their indices, updating the maximum length of subarrays that sum to k by checking if the difference between the current prefix sum and k has been seen before.

Algorithm

1. Initialize Variables: Start with prefix_sum as 0, res as 0, and an empty hash table indices to store the first occurrence of each prefix sum.
2. Iterate through the Array: For each element in the array, update the prefix_sum and check if it equals k to update res. If prefix_sum - k exists in the hash table, compute the potential subarray length and update res if it’s longer.
3. Update Hash Table: Record the index of each prefix sum in the hash table only if it’s not already present, ensuring we store the earliest index to maximize subarray length.

Implement

    class Solution:
  def maxSubArrayLen(self, nums: List[int], k: int) -> int:
      # Input: nums = [1,-1,5,-2,3], k = 3
      # Output: 4
      prefix_sum = 0
      res = 0
      indices = {}
      for i, num in enumerate(nums):
          prefix_sum += num
          if prefix_sum == k:
              res = i + 1
          
          if prefix_sum - k in indices:
              res = max(res, i - indices[prefix_sum - k])
          
          if prefix_sum not in indices:
              indices[prefix_sum] = i 
      
      return res

    
    

Twitter  facebook  Email