esc to dismiss

560. 和为K的子数组

题目

给定一个整数数组和一个整数 k,你需要找到该数组中和为 k 的连续的子数组的个数。

示例 1 :

输入:nums = [1,1,1], k = 2

输出: 2 , [1,1][1,1] 为两种不同的情况。

说明 :

数组的长度为 [1, 20,000]。

数组中元素的范围是 [-1000, 1000] ,且整数 k 的范围是 [-1e7, 1e7]。

解题思路

这套题起初以 滑动窗口 的解法来做,但提交结果报错了,原因是滑动窗口 适合的场景是递增或递减的连续数组求区间,而本题中数组内可以为负数,因此区间的和不是单调的递增或递减,因此不能用滑动窗口,而应该用前缀和。

我首先想到的简单的暴力算法,在官方题解中这种方法叫 “枚举”:

func subarraySum(nums []int, k int) int {
    size := len(nums)
    count := 0
    sum := 0

    for i := 0; i < size; i++ {
        sum = 0
        for j := i; j < size; j++ {
            sum += nums[j]
            if sum == k {
                count++
            }
        }
    }

    return count
}

代码简单,算法暴力,时间复杂度 O(n^2)

前缀和 +哈希优化:

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

    for i := 0; i < size; i++ {
        pre += nums[i]
        count += m[pre - k]
        m[pre] += 1
    }

    return count
}

结题思路为:

前缀和,即计算从开头到当前节点的和,我们定义 pre[i] 为 [0..i][0..i] 里所有数的和。那么可以递推算出每个节点的前缀和:

pre[i]=pre[i−1]+nums[i]

那么我们求子数组和,[j..i] 这个子数组和为 k,我们就可以通过前缀和来转换:

pre[i]−pre[j−1]==k

移动计算项即可得到:

pre[j−1]==pre[i]−k

因此,我们将前缀和存入哈希表中,如果能找到 key 值为pre[i]−k 的项,那就说明找到了满足条件的区间。也就是上述代码中 count += m[pre - k] 所表示的,go语言中如果 map 找不到key会返回默认值(0).

leetcode 官方题解中图形化展示了结题过程:

  1. 首先初始化哈希表: mp[0] = 1 (想想看,为什么要这样初始化?)

  1. 开始从第一个元素计算前缀和(即自己),用前缀和减子数组和去哈希表中查找(3-7 ⇒ mp[-4]),没有找到,count 为0. 并添加本元素的前缀和至哈希表: mp[3] = 1

  1. 遍历到第二个元素,前缀和为7 (3+4), 用前缀和减子数组和去哈希表中查找(7-7 ⇒ mp[0]),找到1个(这就是为什么初始化哈希表的用途),count 加1. 再添加本元素的前缀和至哈希表: mp[7] = 1

  1. 继续,前缀和为14,用前缀和减子数组和去哈希表中查找(14-7 ⇒ mp[7]),找到1个,count 加1. 再添加本元素的前缀和至哈希表: mp[14] = 1

  1. 继续。前缀和为16,用前缀和减子数组和去哈希表中查找(16-7 ⇒ mp[9]),找到0个,count 不变. 再添加本元素的前缀和至哈希表: mp[16] = 1

  1. 继续。前缀和为13,用前缀和减子数组和去哈希表中查找(13-7 ⇒ mp[6]),找到0个,count 不变. 再添加本元素的前缀和至哈希表: mp[13] = 1

  1. 继续。前缀和为14,用前缀和减子数组和去哈希表中查找(14-7 ⇒ mp[7]),找到1个,count 加1. 再添加本元素的前缀和至哈希表: mp[14] = 2 (因为14已经在哈希表中,所以增1)

  1. 继续,解释略。

  1. 继续,解释略。

经验教训

选错算法会很惨。

x