一维数据的两种走法

前面八课练的是三件事：估复杂度、写函数、按容器选操作。这些都是在同一段代码里做替换——把列表换成集合、把三行循环压成一行、把结果用 return 交出去。

这一课处理的是另一种局面：换容器、压写法都已经做到位了，程序还是超时。蓝桥杯里最常见的超时写法是两层循环——「对每个区间求一次和」「对每对元素判断一次条件」。遇到这种题，多数时候只要换一种走法：同样的数据、同样的下标，扫过它的顺序换一下，两层循环就能降成一层。前缀和让区间和一步算出来，双指针让左右两个下标都只往前走、不回头。

这两种走法是后面所有优化技巧的起点。二分、单调队列、滑动窗口最大值、差分，学的都是把某一种「重复用同一批数据」的动作摊平成一遍扫描。这一课先把最基础的两种练熟：一道区间求和的题，写三个版本，把耗时量出来。

一道题，三种走法

题目本身很短。给定 n 个整数组成的数组 a 与一个整数 S，求和恰好等于 S 的连续区间有多少个。

先约定记号。连续区间（子数组）指 a[l], a[l+1], \dots, a[r] 这一段，用闭区间 [l, r] 表示，0 \le l \le r \le n-1。要求的是满足 \sum_{i=l}^{r} a[i] = S 的 (l, r) 有多少对。

最直接的写法是枚举所有区间，每对 (l, r) 都把区间里的数加一遍。下面这个版本换了个加法顺序——固定左端点 l，右端点 r 一路往右扩，边扩边累加——省掉了每个区间重头再算一遍的开销：

def count_brute(a, S):
    n = len(a)
    count = 0
    for l in range(n):
        s = 0
        for r in range(l, n):
            s += a[r]
            if s == S:
                count += 1
    return count

内层循环体跑一次的代价是常数（一次加法、一次比较），跑的次数是所有区间的个数 \frac{n(n+1)}{2}，所以这一版的时间复杂度是 O(n^2)。规模小的时候看不出问题。取 a 为 16 个 1、S = 4，内层一共走 136 步，答案是 13——这个数可以手工数出来：长度 4 的区间有 16-4+1 = 13 个。数据规模换成 n = 16000，区间个数涨到 1.28 亿，本机实测 3.05 秒（本节末尾的表格里）；蓝桥杯常见的 1 秒时限下，这一版交上去就是超时。

前缀和：一次减法出区间和

两个下标 l 与 r 都要动，是这一版慢的原因——区间个数本身就是 n 的平方那么多。要把它降下来，得找一个只需要动一个下标的说法。

数列的前 i 项和是算法竞赛里常用的预处理，叫前缀和。它的定义直接照字面写：

前 i 项和与「下标 i」的关系要看准：pre[i] 是前 i 项的和，所以它装着的是 a[0] 到 a[i-1]。这个约定多出了一个不装任何元素的 pre[0]，表的长度是 n + 1。它的来历可以用递推式说清：既然每一项都由前一项加上一个 a 里的元素得到，

要让这个式子对 i = 0 也成立，就必须有 pre[0] = 0 这个起点。前缀和数组的第 0 位是「还没开始累加」的状态，与列表下标从 0 起是同一件事。

按这个约定，区间 [l, r] 的和是：

理由是两段前缀和相抵：pre[r+1] 是前 r+1 项的和，比区间和多了前 l 项；pre[l] 正好就是那多出来的前 l 项，减掉即可。这个式子里 l 和 r 的地位都一样，不需要为 l = 0 或 r = n-1 补任何特判。若把 pre[i] 定义成「a[0] 到 a[i] 的和」，公式就成了 pre[r] - pre[l-1]，l = 0 时 pre[-1] 会绕到列表末尾——这是最常踩的一处。

def build_pre(a):
    pre = [0]
    for x in a:
        pre.append(pre[-1] + x)
    return pre


a = [3, 1, 4, 1, 5]
pre = build_pre(a)
print(pre)                  # [0, 3, 4, 8, 9, 14]
print(pre[2] - pre[0])      # 4 = a[0] + a[1]
print(pre[5] - pre[2])      # 10 = a[2] + a[3] + a[4]

[0, 3, 4, 8, 9, 14]
4
10

pre[-1] 在 build_pre 里出现时是个合法用法：它是 Python 里「最后一个元素」的写法，指的是刚追加进去的那一项。这与上面那个「pre[-1] 会绕到末尾」是同一个机制的两面，写 a[l-1] 这类下标时一定要确认 l 不会取到 0。

建这张表的代价是 O(n)：一趟循环，每次只做一次加法与一次追加。建好之后，任意区间和的查询只要一次减法，代价 O(1)，与区间有多长无关。

这一步换来的东西可以用第 3 课那张操作价格表说清。那里的结论是列表按下标取元素 O(1)、切片复制 O(k)；这里的对照是：多花 O(n) 的空间存下一张表，把「每个区间各自求和」的 O(k) 换成了一次 O(1) 的减法。空间换时间，换来的是查询次数的上限被抬高了几个数量级。

import random
import time

a = [random.randint(1, 100) for _ in range(100000)]
t0 = time.perf_counter()
pre = build_pre(a)
t1 = time.perf_counter()
print('建前缀和表', t1 - t0, '秒')

建前缀和表 0.004 秒

用前缀和把两层循环降成一层

表已经建好，接下来是「恰好等于 S」这个条件。把区间和公式代进去：

S 是题目给定的，右端点 r 是我们正在扫到的位置，于是 r 固定时右边那个值完全确定：要找的左端点 l，就是那些前缀和等于 \text{pre}[r+1] - S 的位置。 剩下的问题是有几个这样的 l，以及它们各出现了几次。

数「某个值出现过几次」正是第 3 课学的哈希查找：字典的按键查找平均 O(1)，比列表 in 的 O(n) 便宜。一边往右扫，一边把已经见过的前缀和记进字典，每扫到一个 r 就查一次字典：

def count_prefix(a, S):
    pre = build_pre(a)
    seen = {0: 1}
    count = 0
    for r in range(len(a)):
        need = pre[r + 1] - S
        count += seen.get(need, 0)
        seen[pre[r + 1]] = seen.get(pre[r + 1], 0) + 1
    return count

几处细节都要交代清楚：

• seen 里存的是「某个前缀和值在此之前出现过几次」。字典的键是前缀和的值，值是出现次数；键相同的多个 l 会累加在同一个计数里。
• 初值要写 seen = {0: 1}，不能留一个空字典。含义是 pre[0] = 0 已经在字典里出现过一次，对应左端点 l = 0（区间从数组开头算起）。少了这一项，所有从开头开始的区间都会被漏掉。
• seen.get(need, 0) 在键不存在时给出 0，省掉一次 if need in seen 的判断。这两句等价，只是前者更短。
• 每轮先查后记。如果写反了，l = r+1 这种空区间会被算进来。

换成这个走法，两层循环降成了一层：for r 扫一遍，循环体里是常数次字典操作。总代价是「O(n) 建表 + O(n) 次查找」，也就是 O(n)。这一版不受数组内容的限制，元素是负数、是零、数组无序，公式都照样成立。

双指针：两个下标都只往前走

前缀和版已经把两层循环降成一层，代价是额外拿出了一张 n+1 项的表。如果数组里的元素全是正数，还有一条更省的路：双指针，也叫滑动窗口——用两个下标 l \le r 框住一段连续的区间，让它们在数组上同步往右滑。

它的想法是：固定右端点时，区间和随左端点向右移动而变小。既然「和」这个量随两个下标各自单调变化，那就不必为每个区间重新计算，只维护当前窗口的和，按三种情形调整：

• 和小于 S，把 r 往右移一格，把新元素加进来；
• 和等于 S，答案加一，随后把 l 往右移一格，减掉左边那个元素，看下一个位置是否也等于 S；
• 和大于 S，把 l 往右移一格，减掉左边那个元素。

def count_window(a, S):
    n = len(a)
    r = 0
    s = 0
    count = 0
    for l in range(n):
        while r < n and s < S:
            s += a[r]
            r += 1
        if s == S:
            count += 1
        s -= a[l]
    return count

这段代码里 l 由 for 循环一路往右，r 只在 while 里往右，两个下标都不回头。l 走 n 步，r 最多走 n 步，所以循环体一共执行 O(n) 次——两层循环真正降成了一层。while 的条件里除了 s < S 还有 r < n，这是防止 r 越过数组末尾。

双指针省掉了前缀和表那 O(n) 的额外空间，代码也更短。代价是它多了一条前提，这条前提在题目里看不出来，只能自己去判断。

前提：和必须随窗口单调

上面的调整规则里，藏着一个用得很顺、却很容易忘掉的前提。

「和小于 S 就把 r 往右移」之所以有效，是因为右边新加进来的元素会让和变大。「和大于 S 就把 l 往右移」之所以有效，是因为左边丢掉的那个元素会让和变小。两条都成立，才保证和这个量随着窗口滑动有规律地变化，可以用「现在偏小就右扩、现在偏大就左缩」这套规则逼近 S。这在元素全为正数时恒成立：加一个正数一定变大，减一个正数一定变小。

元素里出现负数，这两条都不再成立。加一个负数会让和变小，减一个负数会让和变大，于是窗口要么偏小、要么偏大，都不在原地的调整方向上。更直接的后果在下标上：左指针必须往右走，那么原来已经被右指针扔在身后、在左指针左边的那些位置，就再也回不来了；而某些答案恰恰要从那里取左端点。「右指针只加不减」这个约束，在有负数时会把解漏掉。

本机实测的三个反例，三个版本各自的答案：

前两组里双指针都少算了一个：开头那个元素是正数，左指针很快把它丢掉了；等到右端点扩到能让总和等于 S 的位置时，那个必需的左端点已经在左指针左边。第三组恰好蒙对——检查代码可以发现，它靠的是循环末尾那次减法之后和正好等于 S，也就是先减后判；把这一步的顺序改一改，它同样会漏。这类「有时对、有时错」的版本比稳定的错版更难查，因为样例上跑出来是对的。

前缀和版没有这条前提：它用减法定义区间和，与元素的正负、数组有没有序都无关。代价是那张 O(n) 的表。

同一道题的三个版本

三个版本到齐，把同一批数据上的耗时摆在一起。数组是 n 个 1 到 100 之间的随机整数，S 取 n，三种走法各跑三次取最小值：

表里两组数字要分开读：

• 看暴力那一列往下走。 n 从 8000 翻到 16000，耗时从 0.681 秒涨到 3.050 秒，是 4.5 倍。这就是 O(n^2) 的样子：规模翻一倍，耗时翻四倍左右。按第 2 课那把尺子，1 秒时限下这一版只能扛到 n \approx 9000 上下。
• 看后两列之间的关系。 同样翻一倍，前缀和从 0.001239 秒到 0.002436 秒，约 2 倍，正好是 O(n) 该有的样子；双指针那一列也是 2 倍。整张表从 n = 2000 到 n = 16000 规模涨了 8 倍，暴力涨了 71 倍，两个线性版本各涨 7 倍左右。

在 n = 16000 这一行，三种走法的差距是 3.050 秒与 0.0024 秒，约 1250 倍——三个数量级。这个差距不是靠换更快的机器、或者把 Python 代码写得更紧凑挣来的，三个版本都是普通写法；差距全部来自走法的改变。

三个版本该选哪一个，按两条判断：

1. 数组是不是全为正数（或至少非负），题目的条件里有没有别的单调结构。是，双指针能写到 O(n)，还省下 O(n) 的空间。
2. 要不要反复回答区间和的查询。若是「先给一批查询、再逐个回答」，前缀和的 O(n) 建表加每次 O(1) 查询是最省力的写法：n = 2000、两万次查询，逐个累加要 0.270 秒，前缀和一次减法只要 0.0022 秒，约 121 倍。

两个版本都还用着列表、字典、循环和函数这些前面学过的东西——第 3 课的价格表与第 4 课的抽函数手法，正是这一课的地基。

三个版本写成函数对照

上一节的三段代码已经分散地出现过，把它们按第 4 课的规矩收成函数：每个函数只管一件事——建表、算答案、把答案打印出来——输入输出都写在定义那一行。

import random


def build_pre(a):
    """前缀和表：pre[0] = 0，pre[i] = pre[i-1] + a[i-1]。"""
    pre = [0]
    for x in a:
        pre.append(pre[-1] + x)
    return pre


def count_brute(a, S):
    """两层循环：枚举所有区间。"""
    n = len(a)
    count = 0
    for l in range(n):
        s = 0
        for r in range(l, n):
            s += a[r]
            if s == S:
                count += 1
    return count


def count_prefix(a, S):
    """前缀和加字典：O(n) 建表，一遍扫描回答。"""
    pre = build_pre(a)
    seen = {0: 1}
    count = 0
    for r in range(len(a)):
        need = pre[r + 1] - S
        count += seen.get(need, 0)
        seen[pre[r + 1]] = seen.get(pre[r + 1], 0) + 1
    return count


def count_window(a, S):
    """双指针：只在元素全为正数时可用。"""
    n = len(a)
    r = 0
    s = 0
    count = 0
    for l in range(n):
        while r < n and s < S:
            s += a[r]
            r += 1
        if s == S:
            count += 1
        s -= a[l]
    return count


def check_three_ways(a, S):
    """同一批数据上跑三个版本，比对答案并打印耗时。"""
    import time
    t0 = time.perf_counter()
    c1 = count_brute(a, S)
    t1 = time.perf_counter()
    c2 = count_prefix(a, S)
    t2 = time.perf_counter()
    c3 = count_window(a, S)
    t3 = time.perf_counter()
    s1 = f'{t1 - t0:.3f}'
    s2 = f'{t2 - t1:.6f}'
    s3 = f'{t3 - t2:.6f}'
    print('暴力', s1, '秒  前缀和', s2, '秒  双指针', s3, '秒')
    print('答案', c1, c2, c3)
    return c1 == c2 == c3


random.seed(20261005)
a = [random.randint(1, 100) for _ in range(8000)]
print(check_three_ways(a, 8000))

暴力 0.686 秒  前缀和 0.001576 秒  双指针 0.000540 秒
答案 163 163 163
True

把三个版本抽成函数之后，对拍就成了一件顺手的事：count_brute 是只有两层循环的直白实现，正确性一眼能看清，用它当参照，count_prefix 与 count_window 都拿同一批随机数据去比对答案。这正是第 8 课那道「先把暴力写对」的用法——暴力解除了保底分，还是验证优化版的基准。上面的 check_three_ways 在 400 组随机小数组上跑过，三个版本答案不一致的组数是 0。

注意 count_prefix 里没有用 random，但整个脚本开头 import random 就够——函数里用到的名字会先找局部、再找全局，第 4 课讲过这一条。check_three_ways 内部又 import time 了一次，放在函数里是为了让它自己不依赖文件顶部还 import 过什么，两种写法都对。

这一课用到的写法

把本课的写法与边界收在一张表里，以后写这类题随手查。

这一类题在省赛里出现频率最高，题目话术通常落在「连续区间」「子数组」「和恰好等于」「和不大于」这几处。看到这类话术，第一步是估规模：允许 O(n^2) 就直接写暴力版，规模上到 10^4 以上就换前缀和，元素全为正数时可以考虑双指针。下一课学栈与队列，用的还是这一课练成的手感——用一对下标或一个容器记录「正在处理哪一段」。

配套项目「AI 刷题助手」在这里要能给出第二层建议：不只推荐算法名，还要说明这题的数据范围下该用哪种走法、以及那种走法的前提在当前题面上是否满足。

• OI Wiki · 前缀和与差分前缀和与差分的权威口径；本课的记号照它走，数组下标从 0 起，于是 pre[0] = 0、pre[i] 是前 i 项和
• Python 官方文档 · 数据结构列表的下标、append、切片与字典查找，本课各操作的官方说法出自这里
• OI Wiki · 复杂度时间复杂度与渐近符号的口径，本课「翻倍涨四倍」的读法照它
• 《算法竞赛进阶指南》前缀和与差分本地教材：前缀和、差分与区间操作的推导，可作参考书查