前缀和
把一段区间，变成两个边界。

01LEETCODE 209 / MEDIUM长度最小的子数组

难度：中等 ｜ 核心知识点：前缀和、二分查找、滑动窗口、双指针

题意与约束

给定一个正整数 target 和正整数数组 nums，返回连续子数组中总和至少为 target 的最短长度。如果所有区间都无法达标，返回 0。注意是「大于等于」而非恰好等于。

原题约束：1 ≤ n ≤ 10⁵；1 ≤ nums[i] ≤ 10⁴；1 ≤ target ≤ 10⁹。正数条件是下面两种高效解法的前提。题意及约束见卡片顶部原题链接。

解法一 · 前缀和 + 二分查找

暴力做法枚举左右边界，维护区间累加和，需要 O(n²)。先用前缀和把每个区间的计算变为相减，再利用正数形成的有序性，便能避免枚举全部右边界。

固定左边界 left，寻找最小的右边界 right，使 P[right] − P[left] ≥ target，等价于在 P 中查找第一个不小于 P[left] + target 的位置。因为 nums 中每一项为正，P 严格递增，bisect_left 可以完成这个 lower_bound 查询。

from bisect import bisect_left
from typing import List


class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        n = len(nums)
        prefix = [0] * (n + 1)
        for i, x in enumerate(nums):
            prefix[i + 1] = prefix[i] + x

        best = n + 1
        for left in range(n):
            need = prefix[left] + target
            right = bisect_left(prefix, need, left + 1)
            if right <= n:
                best = min(best, right - left)

        return 0 if best == n + 1 else best

关键代码解释

• prefix[i + 1] 把 nums[i] 纳入前缀，避免遗漏第一个元素。
• bisect_left(prefix, need, left + 1) 从 left 后的边界开始查找，保证子数组非空。它返回的是前缀数组下标。
• prefix 长度为 n + 1：查找失败会返回 n + 1；right = n 仍是合法边界，代表区间延伸至末尾。
• best = n + 1 表示尚无解，最后统一转成 0。

示例推演 · 前缀数组 [0,2,5,6,8,12,15]

正确性：对于固定左端点，二分找到的首个合格右边界给出该左端点下的最短区间。对所有左端点取最小值，就是全局最短长度。

解法二 · 滑动窗口（面试首选）

正数还保证了窗口的单调性：右端加入元素，总和变大；左端移出元素，总和变小。右端每走一步，只要当前窗口已达标，就先记录答案，再持续缩短左端，直到再次不达标。

循环使用闭区间 [left,right]。虽然与前缀数组的 [l,r) 写法不同，但含义是明确的：窗口长度为 right − left + 1，移出元素前先更新答案。

from typing import List


class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        n = len(nums)
        left = 0
        total = 0
        best = n + 1

        for right, x in enumerate(nums):
            total += x
            while total >= target:
                best = min(best, right - left + 1)
                total -= nums[left]
                left += 1

        return 0 if best == n + 1 else best

关键代码解释

• while total >= target 保证一次右移后能尝试所有仍达标的更短窗口，不能换成单次 if。
• total -= nums[left] 必须在 left 自增之前，移走的才是窗口旧左端点。
• total 始终维护当前窗口的和，无需重复求和或创建切片。

示例推演 · target = 7

正确性与循环不变量：每次记录时 total 就是 [left,right] 的和。每次 while 结束，窗口已不达标。被移出的旧左端点在当前 right 下已经考察过；将来 right 更大时，沿用它只会得到更长的窗口，所以可以永久丢弃。所有可能改善答案的窗口都会被覆盖。

解法比较

易错点与边界检查

• 判定条件是 ≥，示例 [4,3] 的和恰好为 7 也必须接受。
• 无解时返回 0，不能返回 n + 1 或负数。
• 单元素刚好达标：target=4，nums=[4] → 1；单元素不足：target=4，nums=[3] → 0。
• 整个数组才达标：target=6，nums=[1,2,3] → 3。
• 负数会破坏窗口推理。例如 target=3，nums=[1,-1,3]：上述窗口会停留在长度 3，漏掉 [3]。该输入不属于 209 的约束，不能把算法无条件推广。
• 二分查找右边界时，比较的是 P[left] + target，而非 target 本身。

02LEETCODE 560 / MEDIUM和为 K 的子数组

难度：中等 ｜ 核心知识点：前缀和、哈希表、频次计数、先查询后插入

题意与约束

给定整数数组 nums 和整数 k，统计有多少个连续、非空子数组的元素和等于 k。不同下标区间分别计数，即使它们的元素值相同。

原题约束：1 ≤ n ≤ 2 × 10⁴；−1000 ≤ nums[i] ≤ 1000；−10⁷ ≤ k ≤ 10⁷。允许负数、零和负目标值。题意及约束见卡片顶部原题链接。

解法一 · 枚举左端点，向右累加（建立基线）

固定 left 后，把右端点逐步向右移动，每次只添加一个新元素。当累加和恰好为 k 时计数。不要因为当前和超过 k 就 break，后面可能有负数把总和拉回来。

from typing import List


class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        count = 0
        n = len(nums)
        for left in range(n):
            total = 0
            for right in range(left, n):
                total += nums[right]
                if total == k:
                    count += 1
        return count

关键代码：total 在每次开始新的 left 时清零，内层循环增量维护 [left,right] 的和。对 [1,1,1]、k=2，left=0 时在 right=1 命中一次，left=1 时在 right=2 命中一次，left=2 无命中，最终为 2。

正确性：每个非空区间都由唯一的一对 left、right 决定，两层循环恰好枚举一次，没有遗漏或重复。

这份代码适合验证思路和小规模对拍；原题上限下可能超时。若每次改成 sum(nums[left:right+1])，最坏会退化到 O(n³)。

解法二 · 前缀数组 + 枚举边界（公式桥梁）

先构建 P，再枚举所有满足 0 ≤ left < right ≤ n 的前缀边界，检查 P[right] − P[left] 是否为 k。这个版本没有减少区间数量，但清楚展示了从「子数组」到「前缀对」的映射，为下一步优化做准备。

from typing import List


class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        n = len(nums)
        prefix = [0] * (n + 1)
        for i, x in enumerate(nums):
            prefix[i + 1] = prefix[i] + x

        count = 0
        for right in range(1, n + 1):
            for left in range(right):
                if prefix[right] - prefix[left] == k:
                    count += 1
        return count

关键代码：range(right) 只枚举严格位于当前右边界之前的 left，排除空区间。[1,1,1] 的 P=[0,1,2,3]，满足差为 2 的边界对为 (0,2)、(1,3)，输出 2。

正确性：每个 [left,right) 与一对前缀边界一一对应，区间和公式直接给出判断条件。

解法三 · 前缀和 + 频次哈希表（推荐）

固定当前右边界 right，把等式移项：

现在只需知道：在当前边界之前，值为 P[right]−k 的前缀出现了多少次。每出现一次，就对应一个不同的合法左端点。用字典 freq 记录频次，让查询从扫描历史前缀变成平均 O(1)。

1. 初始 freq = {0: 1}，登记一次空前缀。
2. 读入 x，更新当前前缀 running。
3. 将历史 running − k 的出现次数加入答案。
4. 最后登记当前 running，供后面的右边界使用。

from typing import List


class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        freq = {0: 1}  # 空前缀，代表从数组开头开始的区间
        running = 0
        count = 0

        for x in nums:
            running += x
            count += freq.get(running - k, 0)
            freq[running] = freq.get(running, 0) + 1

        return count

关键代码解释

• freq.get(running - k, 0) 查的是所需历史前缀值，不是查询 k，也不是 running 本身。
• 查到的是频次，所以直接累加这个数量；不能只加 1，也不能使用只表示「存在」的集合。
• 必须先查历史再登记当前。否则 k=0 时会将当前前缀与自身配对，错误地计入空区间。
• 只维护 running，无需保存整个 P 数组；字典仍可能有 O(n) 个不同的前缀值。

示例推演 A · nums=[1,1,1]，k=2

示例推演 B · nums=[1,-1,0]，k=0

前缀边界的和值依次为 [0,1,0,0]。最后一个 0 到来之前，历史已经有两个和值为 0 的前缀，当前一步就应增加 2 个答案。

为什么一定正确？

处理 P[right] 时，字典恰好记录 P[0] 到 P[right−1] 的频次，这是循环不变量。每个被查到的 P[left] 都满足 left < right 和差为 k，因此对应一个合法非空子数组；反过来，每个合法子数组都会在其右边界被查询到。按右边界分组，区间既不重复也不遗漏。登记当前前缀后，不变量对下一轮继续成立。

上述时间分析使用常规哈希表平均复杂度模型；不是哈希冲突极端情况下的最坏界。

解法比较

易错点与边界检查

• 遗漏空前缀：nums=[3]、k=3 应输出 1。没有 {0:1} 就会漏掉它。
• 先插再查：nums=[0]、k=0 应输出 1。错误顺序会得到 2。
• 把频次当布尔值：nums=[0,0,0]、k=0 应输出 6，即 3×4/2；三个右边界各贡献 1、2、3。
• 遇到超出 k 就停止：nums=[3,-2]、k=1 应输出 1，扫描到 3 时不能提前结束。
• 把子数组当子序列：nums=[1,2,1]、k=2 只有 [2] 合法，不能跳过中间的 2 拼出 [1,1]。
• 负目标：nums=[-1,-1,1]、k=-1 → 3。Python int 可以容纳答案；换到固定宽度语言时应关注 n(n+1)/2 的上界。

03LEETCODE 238 / MEDIUM除自身以外数组的乘积

难度：中等 ｜ 核心知识点：前缀乘积、后缀乘积、空积为 1、输出数组复用

题意与约束

返回数组 answer，其中 answer[i] 等于 nums 中除 nums[i] 以外所有元素的乘积。要求不使用除法，并在 O(n) 时间内完成；进阶要求 O(1) 额外空间，输出数组不计入额外空间。

原题约束：2 ≤ n ≤ 10⁵；−30 ≤ nums[i] ≤ 30，允许零与负数。原题保证相关前缀、后缀乘积及答案在 32 位整数范围内。力扣当前标题为「除了自身以外数组的乘积」，与题单中的写法对应同一题。

解法一 · 显式保存左右乘积

定义 left[i] 为 i 左侧所有元素的乘积，right[i] 为 i 右侧所有元素的乘积，二者都不包含 nums[i]。空集合的乘积为 1，所以 left[0]=1、right[n−1]=1。

from typing import List


class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        left = [1] * n
        right = [1] * n

        for i in range(1, n):
            left[i] = left[i - 1] * nums[i - 1]
        for i in range(n - 2, -1, -1):
            right[i] = right[i + 1] * nums[i + 1]

        return [left[i] * right[i] for i in range(n)]

关键代码与示例推演

nums[i - 1] 和 nums[i + 1] 是「排除自己」的关键。计算 left 从左向右，计算 right 从右向左，保证依赖的状态已经就绪。对 nums=[1,2,3,4]：

正确性：递推式分别构造左右两侧的乘积；两段不相交且并集恰好是除 i 以外的所有位置，将它们相乘就是定义要求的答案。

解法二 · 输出数组存左积，单变量维护右积（推荐）

最终答案还未生成时，answer[i] 可以先存 i 左侧乘积。再从右向左扫描，用 suffix 保存 i 右侧乘积，直接乘进 answer[i]，就不需要 right 数组。

正向循环开始处理 i 时，prefix 恰好是不含 i 的左积；反向循环开始处理 i 时，suffix 恰好是不含 i 的右积。两轮都必须先使用旧状态，再把 nums[i] 纳入累计。

from typing import List


class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        answer = [1] * n

        prefix = 1
        for i in range(n):
            answer[i] = prefix
            prefix *= nums[i]

        suffix = 1
        for i in range(n - 1, -1, -1):
            answer[i] *= suffix
            suffix *= nums[i]

        return answer

关键代码解释

• answer[i] = prefix 放在 prefix *= nums[i] 之前，确保左积不包含当前元素。
• range(n - 1, -1, -1) 的结束边界 −1 不包含在遍历中，所以最后会处理 i=0。
• answer[i] *= suffix 使用当前右积后，再纳入 nums[i]；顺序反过来会把自身错误乘入。
• 代码没有修改输入数组，答案是一个新列表。

示例推演 · 两次扫描

正向扫描时，prefix 依次以 1、1、2、6 写入 answer，得到 [1,1,2,6]，然后反向合并：

零元素推演：nums=[-1,1,0,-3,3]，正向得到 [1,-1,-1,0,0]。反向访问 i=4、3、2、1、0 时，使用前的 suffix 分别为 1、3、−9、0、0；相乘后得到 [0,0,9,0,0]。零在扫描中自然传播。

正确性：第一轮归纳保证 answer[i] 为左侧乘积；第二轮归纳保证使用前 suffix 为右侧乘积。因此更新后的每项与解法一完全相同，压缩的是存储方式，状态定义未变。

复杂度采用题目规定范围下的整数运算模型。输出数组有 n 项，不能把「O(1) 额外空间」说成总空间 O(1)。

解法比较

易错点与边界检查

• 累计初值是 1，不是 0；乘法的单位元与加法不同。
• 不要用前缀总积相除来求区间乘积，零会导致信息丢失，且本题禁止除法。
• 没有零：[2,3] → [3,2]，同时检查首尾的空积。
• 只有一个零：[0,2,3] → [6,0,0]；两个零：[0,0,3] → [0,0,0]。
• 负数：[−1,2,−3] → [−6,3,−2]，按正常乘法处理符号。
• 切片和逐项重算乘积会造成 O(n²)，不满足线性要求。