Leetcode: Maximum Size Subarray Sum Equals k

Maximum Size Subarray Sum Equals k


<a href=”https://github.com/dennyzhang/code.dennyzhang.com/tree/master/problems/example“><img align=”right” width=”200″ height=”183″ src=”github.png” /></a>

Similar Problems:


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.

Example 2:

Input: nums = [-2, -1, 2, 1], k = 1
Output: 2 
Explanation: The subarray [-1, 2] sums to 1 and is the longest.

Follow Up:

  • Can you do it in O(n) time?

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.


  • Solution:
// Blog link: https://code.dennyzhang.com/example
// Basic Ideas: presum + hashmap + onepass
//   m(i) -> the first index which can get the presum of i
// Complexity: Time O(n), Space O(n)
func maxSubArrayLen(nums []int, k int) int {
    preSum := make([]int, len(nums)+1)
    sum := 0
    m := map[int]int{0:-1}
    res := 0
    for i, num := range nums {
        sum += num
        preSum[i] = sum
        _, ok := m[sum]
        if !ok {
            m[sum] = i
        }
        j, ok := m[sum-k]
        if ok && i-j > res {
            res = i-j
        }
    }
    return res
}

<div style=”overflow: hidden;”>

<div style=”float: left; padding: 5px”> <a href=”https://www.linkedin.com/in/dennyzhang001“><img src=”linkedin.png” alt=”linkedin” /></a></div>

<div style=”float: left; padding: 5px”><a href=”https://github.com/dennyzhang“><img src=”github.png” alt=”github” /></a></div>

<div style=”float: left; padding: 5px”><a href=”https://www.dennyzhang.com/slack” target=”_blank” rel=”nofollow”><img src=”slack.png” alt=”slack”/></a></div>

</div>


Share It, If You Like It.

Leave a Reply

Your email address will not be published.