子串题解——和为 K 的子数组【LeetCode】

谨记： 数组不是单调的话，不要用滑动窗口，考虑用前缀和

写法一：两次遍历

代码的核心思想是通过 前缀和 和 哈希表 来高效地统计符合条件的子数组个数。具体步骤如下：

1. 计算前缀和数组 s：

   • s[i] 表示 nums 的前 i 个元素的和。
   • s[0] = 0，表示前 0 个元素的和为 0。
   • 例如，nums = [1, 1, 1]，则 s = [0, 1, 2, 3]。

2. 使用 defaultdict 记录前缀和出现的次数：

   • defaultdict(int) 是一个字典，默认值为 0。如果访问一个不存在的键，会返回 0，而不是抛出异常。
   • cnt[sj] 表示前缀和 sj 出现的次数。

3. 遍历前缀和数组 s，统计符合条件的子数组个数：

   • 对于每个前缀和 sj，检查是否存在前缀和 sj - k。
     • 如果存在，则说明从某个位置到当前位置的子数组和为 k。
     • 将 cnt[sj - k] 的值加到 ans 中。
   • 将当前前缀和 sj 记录到 cnt 中。

from collections import defaultdict

class Solution(object):
    def subarraySum(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        # 1. 计算前缀和数组 s
        s = [0] * (len(nums) + 1)  # s[0] = 0，表示前 0 个元素的和为 0
        for i, x in enumerate(nums):
            s[i + 1] = s[i] + x  # s[i+1] = s[i] + nums[i]

        # 2. 初始化结果和哈希表
        ans = 0  # 记录符合条件的子数组个数
        cnt = defaultdict(int)  # 哈希表，记录前缀和出现的次数

        # 3. 遍历前缀和数组，统计符合条件的子数组个数
        for sj in s:
            # 如果存在 s[i] = sj - k，则说明从 i+1 到 j 的子数组和为 k
            ans += cnt[sj - k]
            # 将当前前缀和 sj 记录到哈希表中
            cnt[sj] += 1

        return ans  # 返回结果

写法二：一次遍历

• 前缀和：使用变量 s 动态计算当前的前缀和。
• 哈希表：使用哈希表 cnt 记录前缀和出现的次数。
• 核心思想：对于当前前缀和 s，检查是否存在前缀和 s - k。如果存在，则说明从某个位置到当前位置的子数组和为 k。

核心逻辑

1. 更新前缀和：
   • s += x：将当前元素 x 加到前缀和 s 中。
2. 检查是否存在 s - k：
   • 如果 cnt[s - k] 存在，则说明从某个位置到当前位置的子数组和为 k。
   • 将 cnt[s - k] 的值加到 ans 中。
3. 记录当前前缀和：
   • cnt[s] += 1：将当前前缀和 s 记录到哈希表中。

from collections import defaultdict

class Solution(object):
    def subarraySum(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        ans = s = 0  # ans 记录结果，s 记录当前前缀和
        cnt = defaultdict(int)  # 哈希表，记录前缀和出现的次数
        cnt[0] = 1  # 初始化，s[0]=0 出现了一次

        # 遍历数组，动态计算前缀和
        for x in nums:
            s += x  # 更新当前前缀和
            # 如果存在 s - k，则说明从某个位置到当前位置的子数组和为 k
            ans += cnt[s - k]
            # 将当前前缀和 s 记录到哈希表中
            cnt[s] += 1

        return ans  # 返回结果