基本信息

  • 题号：560
  • 题厂：脸书
  • 难度系数：中


已知一个数组，问数组里面有多少 subarray 的和等于 k。

例如：nums = [1,2,3], k = 3

1 + 2 = 3， 3 = 3，所以返回 2。

subarray 需要连续且不为空

解题思路

  • 本题看似简单，其实略难。如果想不到 prefix 很容易卡壳
  • 本题我们需要算出之前元素的和，再根据当前 sum 和之前的差距算出有多少种配对方式……
  • 如何根据 prefix 找出算法，最终又归结于 data pattern 寻找规律上😳


class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        # 初始返回值 res
        res = 0
        # 创建变量，计算当前变量
        curSum = 0

        # hashmap 用来记录各种 prefix 的数量，为解题关键
        # prefix: count
        # 进入 for 循环之前，初始化前缀和为 0 的时候有 1 种可能——即：数组开头第 -1 个元素，什么元素都没有前缀和此时为 1
        prefixSum = { 0: 1 }
        
        for n in nums:
            curSum += n
            # 计算当前和与目标 k 之间的差距
            diff = curSum - k
            # 如果此时 hashmap 有对应差距的记录，则说明有 x 种可能满足 diff + k = curSum
            res += prefixSum.get(diff, 0)
            
            # 更新 prefix，用于下一次计算……
            prefixSum[curSum] = 1 + prefixSum.get(curSum, 0)
            
        return res


Constraints

  • 1 <= nums.length <= 2 * 104
  • -1000 <= nums[i] <= 1000
  • -107 <= k <= 107

本题需要引入 「 prefix 前缀和」 的一个原因就是 k 和数组元素可以为负……


Big O

  • Time：O（n）
  • Space：引入 hashmap，故 O（n）


测试

  • 有满足的 subarray 相加和等于 k，有多重状况同时满足，检查算法是否有疏漏
  • 不满足的状况


总结

虽然最终代码不复杂，也没有涉及高级数据结构，但思路挺绕……虽然 brute force 明显可以用来解题，但考点明显是 prefix……😵

基于解体思路，需要定期回顾深入理解 prefix 的精髓……🙈