Leetcode: Continuous Subarray Sum

Continuous Subarray Sum


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

Similar Problems:


Given a list of non-negative numbers and a target integer k, write a function to check if the array has a continuous subarray of size at least 2 that sums up to the multiple of k, that is, sums up to n*k where n is also an integer.

Example 1:

Input: [23, 2, 4, 6, 7],  k=6
Output: True
Explanation: Because [2, 4] is a continuous subarray of size 2 and sums up to 6.

Example 2:

Input: [23, 2, 6, 4, 7],  k=6
Output: True
Explanation: Because [23, 2, 6, 4, 7] is an continuous subarray of size 5 and sums up to 42.

Note:

  1. The length of the array won’t exceed 10,000.
  2. You may assume the sum of all the numbers is in the range of a signed 32-bit integer.

Github: code.dennyzhang.com

Credits To: leetcode.com

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


// Blog link: https://code.dennyzhang.com/continuous-subarray-sum
// Basic Ideas: presum + mod + first occurence
// Complexity: Time O(n), Space O(k)
func checkSubarraySum(nums []int, k int) bool {
    if k<0 { k = -k }
    m := map[int]int{0:-1}
    for preSum, i:=0, 0; i<len(nums); i++ {
        preSum += nums[i]
        if k !=0 { preSum = preSum%k }
        _, ok := m[preSum]
        if !ok {
            m[preSum] = i
        } else {
            if i-m[preSum] >= 2 {
                return true
            }
        }
    }
    return false
}

<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.