esc to dismiss

523. 连续的子数组和

题目

给定一个包含 非负数 的数组和一个目标 整数 k ,编写一个函数来判断该数组是否含有连续的子数组,其大小至少为 2,且总和为 k 的倍数,即总和为 n * k ,其中 n 也是一个整数。

示例 1:

输入:[23,2,4,6,7], k = 6

输出:True

解释:[2,4] 是一个大小为 2 的子数组,并且和为 6

示例 2:

输入:[23,2,6,4,7], k = 6

输出:True

解释:[23,2,6,4,7]是大小为 5 的子数组,并且和为 42

解体思路

官方题解第三种给了很巧妙的方式,利用前缀和 +哈希表优化。

560. 和为K的子数组 题解题思路也是前缀和+哈希表,但盖提哈希表存的就是前缀和,容易理解。而本题的关键是:哈希表中要存 “前缀和除以目标数 k 的余数”。

先看最终代码:

func checkSubarraySum(nums []int, k int) bool {
    size := len(nums)
    pre := 0
    m := make(map[int]int)
    m[0] = -1

    for i := 0; i < size; i++ {
        pre += nums[i]
        if k != 0 {
            pre = pre % k
        }
        if j, ok := m[pre]; ok {
            if i-j > 1 {
                return true
            }
        } else {
            m[pre] = i
        }

    }

    return false
}

为什么哈希表中存“前缀和除以k的余数呢”?这样看,如果遍历到了下标i,前缀和除以k,用这个结果去哈希表中查,如果找到值(即下标)j,说明下标为 j 的前缀和除k也余同样的数,那么 j 到 i 的和即可以被 k 整除。由于题目要求至少区间大小为2,因此加上个限定条件: if i-j > 1

下面以官方题解图示来解释:

  1. 初始化哈希表 m[0] = -1 (想想为什么)

  1. 从头开始遍历,第一个元素前缀和为2,除k(13)余2,存到哈希表 m[2] = 0(键为余数,值为下标)。

  1. 第二个元素,前缀和为7,除13余7,存储哈希表 m[7] = 1。

  1. 第三个元素,前缀和40,除13余1,存入哈希表 m[1] = 2

  1. 第四个元素,前缀和为46,除13余7;从哈希表中查找,找到一个值,下标为1.

  1. 找到的这个下标到当前的元素即组成了满足条件的子数组:33 和 6 和为39,正好可被13整除。

经验教训

暴力解法或官方提供的第二种前缀和时间复杂度都有O(n^2), 会超时。

func checkSubarraySum(nums []int, k int) bool {
    size := len(nums)
    sum := 0
    for i := 0; i < size; i++ {
        sum = nums[i]
        for j := i + 1; j < size; j++ {
            sum += nums[j]
            if sum%k == 0 {
                return true
            }
        }
    }

    return false
}
x