523.md

Continuous Subarray Sum

题目

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 a multiple of k, that is, sums up to n*k where n is also an integer.

EExample 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:

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

总结    

    dp问题， 问题的结果依赖于多个变量。如何使用多个变量(转化使用方式)是优化该题性能的关键。

代码

版本1

func checkSubarraySum(nums []int, k int) bool {
    if len(nums) <= 1 {
        return false
    }
    dp := make([]int, len(nums))
    dp[0] = nums[0]
    for i := 1; i < len(nums); i++ {
        dp[i] = nums[i]
        for j := 0; j < i; j++ {
            dp[j] += nums[i]
            if dp[j] == 0 || (k != 0 && dp[j] % k == 0) {
                return true
            }
        }
    }
    return false
    
}

版本2

func checkSubarraySum(nums []int, k int) bool {
    if len(nums) <= 1 {
        return false
    }
    dp := make(map[int]int, len(nums))
    if k != 0 {
        dp[nums[0]%k] = 0
    } else {
        dp[nums[0]] = 0
    }
    sum := nums[0]
    for i := 1; i < len(nums); i++ {
        sum += nums[i]
        if k != 0 {
            sum %= k
        }
        if sum == 0 {
            return true
        }
        j, ok := dp[sum]
        if ok && i-j >= 2 {
            return true
        } 
        if !ok {
            dp[sum] = i    
        }
    }
    return false
}