算法面试：从规格到反例与可验证实现

算法面试考察的是在约束下建立正确解法的过程。先确认输入、输出、重复含义和规模，再给基线与改进理由，能让讨论围绕可验证的东西展开。知识点正文已经讲过的算法，在这里通过一个原创问题串起思考步骤。

原创问题：和为目标的连续区间

给定整数列表和目标值，统计非空连续区间的数量，区间和等于目标。允许负数、零和重复值；输出是区间数量，不是不同的元素组合。举例 [2,-2,2]、目标2，有三个区间：两个单元素2，以及完整列表。

最直接枚举左右端点，再从头求和会达到 O(n³)；每次固定左端并逐步累加右端，可以降到 O(n²)。这个基线足以验证短输入，也提示我们需要复用区间和。

用前缀差重新表述

设当前前缀和为P。某个此前前缀和Q满足 P-Q=target 时，两者之间形成一个合法区间，所以需要知道历史中 P-target 出现过多少次。哈希表保存前缀和频数，扫描一次即可。

def count_target_ranges(values, target):
    frequencies = {0: 1}
    prefix = answer = 0
    for value in values:
        prefix += value
        answer += frequencies.get(prefix - target, 0)
        frequencies[prefix] = frequencies.get(prefix, 0) + 1
    return answer


if __name__ == '__main__':
    print(count_target_ranges([2, -2, 2], 2))
    print(count_target_ranges([0, 0], 0))

初始频数 {0:1} 代表列表开始之前的空前缀，能统计从下标0开始的区间。先查询再记入当前前缀，排除同一前缀与自身配对形成的空区间。[0,0]、目标0结果为3，若把频数仅保存为集合，就会丢失重复前缀对应的不同区间。

每个合法区间有唯一右端点；扫描该右端点时，左侧边界的前缀已经记录，且按频数恰好计入一次。因此结果不重不漏。平均时间 O(n)，额外空间 O(n)。

什么时候该换一种题型模型

本题允许负数，普通“和大了就左移”的滑窗规则不成立。与其记住“连续区间用滑窗”，不如检查移动指针是否有可证明的单调作用。类似地，“有重复子问题”也不足以直接确定DP状态和转移。

在白板与代码间保持含义一致

先用小例子手算，再写循环不变量，最后选择半开或闭区间。写完检查空输入、最小规模、全相等、极端正负值和边界返回值。Python整数不会固定宽度溢出，但长整数仍有成本；递归还可能遇到调用栈限制。

不必把每次讨论变成完整生产系统。若问题要求返回全部区间，输出数量可能 Θ(n²)，此时线性时间目标本身就不现实；若要求在线流式统计，可以持续保留前缀频数，但内存仍可能随不同前缀数量增长。

练习与复盘

写O(n²)基线并随机对拍，再把输出改为最长合法区间长度，思考同一前缀应该保留最早位置还是所有位置。复盘记录触发条件、错因与能暴露它的最小反例，不只记录题目编号。

面试自查：为什么空前缀需要一次初始计数；为什么频数查询必须在更新前；负数破坏的是滑窗的哪条推理；若要返回区间本身，复杂度结论怎样改变。练习以这里的原创规格为准，外部题目只作为额外练习入口。

本地运行

示例仅使用 Python 标准库，适用于 Python 3.10 及以上。把 example.py 与 test_example.py 保存到同一个目录，在该目录运行：

python example.py
python -m unittest -v test_example.py

测试检查本文列出的边界；新增练习仍需自己补充断言。

参考资料

• MIT 6.006：问题求解与练习资料
• Python：字典的键与计数