Leetcode - Maximum Size Subarray Sum Equals k

https://leetcode.com/problems/maximum-size-subarray-sum-equals-k/

Given an array nums and a target value k, find the maximum length of a subarray that sums to k. If there isn't one, return 0 instead.

Note:
The sum of the entire nums array is guaranteed to fit within the 32-bit signed integer range.

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.

Use a hash to keep every sum for each i. And then use current_sum - previous_sum to see whether the result is equal to k.

func maxSubArrayLen(nums []int, k int) int {
    if len(nums) == 0 {
        return 0
    }
    hash := map[int]int{}
    maxNum := 0
    sum := 0
    for i := 0; i < len(nums); i++ {
        sum += nums[i]
        if sum == k {
            maxNum = i + 1
        } else {
            if val, ok := hash[sum - k]; ok {
                maxNum = max(maxNum, i - val)
            }
        }
        if _, ok := hash[sum]; !ok {
            hash[sum] = i
        }
    }
    
    return maxNum
}

func max(a, b int) int {
    if a > b {
        return a
    }
    
    return b
}

• 相关文章
• 全局相关文章