题目

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

示例 1 :
输入: nums = [1, 1, 1], k = 2
输出: 2, [1, 1] 与 [1, 1] 为两种不同的情况。

说明 :**

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

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

    方案一（暴力法）

    1. class Solution:
    2.  def subarraySum(self, nums: List[int], k: int) -> int:
    3.      # 暴力法
    4.      count = 0
    5.      for i in range(len(nums)):
    6.          for j in range(i, len(nums)):
    7.              if sum(nums[i:j+1]) == k:
    8.                  count += 1
    10.      return count

  • 时间复杂度 和为K的子数组 - 图1

    方案二（使用哈希表优化）

    1. class Solution:
    2.   def subarraySum(self, nums: List[int], k: int) -> int:
    3.       # 假如存在区间[left,right]，使得在[left,right]这个区间的子数组的和为k。换句话说，就是前right项和减去前left项和等于k，即前left项和等于前right项和减去k。
    4.       # 可以这样做，在扫描数组的同时，假设当前扫到第i位，记录它的前i项和sum，用该和减去k，即sum-k，判断sum-k是否为某个位置的前n项和，若是，更新统计量。
    6.       count, ans = 0, 0
    7.       pre = collections.defaultdict(int)
    8.       pre[0] += 1 # 初始化时，前缀和为 0 出现过 1 次（空的时候）
    10.       for num in nums:
    11.           count += num
    12.           if count - k in pre:
    13.               ans += pre[count - k]
    14.           pre[count] += 1
    16.       return ans

    方法三（动态规划思想）

    1. class Solution:
    2.   def subarraySum(self, nums: List[int], k: int) -> int:
    3.       # 动态规划
    4.       # dp[i] 表示 nums[:i] 之内和为 k 的连续子数组的个数
    5.       dp = [0]
    7.       for index, num in enumerate(nums):
    8.           # 包含当前 num 且和为 k 的连续子数组的个数
    9.           count, amount = 0, 0 # 连续子数组的和，以及和为 k 的数量
    10.           for j in range(index, -1, -1):
    11.               count += nums[j]
    12.               if count == k:
    13.                   amount += 1
    15.           dp.append(dp[-1] + amount)
    17.       return dp[-1]

  • 超时

    原文

    https://leetcode-cn.com/explore/interview/card/2020-top-interview-questions/284/hash-map/1272/
    https://leetcode-cn.com/problems/subarray-sum-equals-k/solution/he-wei-kde-zi-shu-zu-by-leetcode-solution/
    https://leetcode-cn.com/problems/subarray-sum-equals-k/solution/qian-zhui-he-shi-xian-jian-dan-by-jarvis1890/