面试题57（二）：和为s的连续正数序列
以small和big维护连续正整数窗口，利用扩张增和、收缩减和的单调性打印全部目标序列。
学习目标
- 能用 small/big 双指针维护连续正整数窗口，打印全部和为 s 的序列
- 能解释"扩张增和、收缩减和"的单调性保证不漏解
- 能说明窗口上界（(s+1)/2）与 int 溢出的处理
从“15为何有三种拆法”开始
先预测：15可以写成1到5、4到6、7到8三组连续正整数之和。题目要求打印全部和为s的连续正数序列，每组至少包含两个数字。
作者不枚举每个起点和终点，而是用small和big两个指针维护一个↡。初始small为1、big为2，最小合法窗口正好包含两个数。
窗口内所有值之和称为。它只需在边界移动时加一个新big或减一个旧small，无需每轮重新求和。
↡公式锁定问题结构
从正整数a到b的连续序列长度为b减a加1，首尾平均数乘长度就是总和：
令长度为L，且b等于a加L减1，可得到：
这个式子说明每个答案既可由窗口搜索，也可由长度因子枚举推导。作者选择窗口，因为只做加减、容易按起点顺序打印，并自然利用正数单调性。
至少两个数意味着L不小于2。若起点a已经太大，最短窗口a与a加1之和也会超过s：
作者令middle等于1加s后除2，并在small小于middle时继续，正好排除只剩单元素或最短两项已过大的起点。
正数保证两个方向可控
big加1并把新big加入窗口时，加入的是正数，窗口和严格增加；移除small并让small加1时，减去的是正数，窗口和严格减少。
这两条性质就是“正数保证单调移动”。扩张行为称为；收缩行为称为。
| 状态 | 动作 | 单调变化 | 目的 |
|---|---|---|---|
| curSum 小于 s | 加入 big 后继 | 窗口和严格增加 | 寻找更大和 |
| curSum 等于 s | 打印当前闭区间 | 作者随后仍扩张 big | 继续找其他解 |
| curSum 大于 s | 移除 small 并右移 | 窗口和严格减小 | 可连续收缩 |
| small 到达 middle | 最短两数和已超界 | 停止 | 不含单元素序列 |
若允许0或负数，扩张可能不增加、收缩也可能反向改变和，当前比较就无法决定唯一移动方向。一般含负数的连续子数组和应使用前缀和与哈希等方法，不能直接套本题窗口。
忠实还原作者控制流
作者在sum小于3时直接返回，因为最小的两个连续正整数1加2已经等于3。
void PrintContinuousSequence(
int small,
int big);
void FindContinuousSequence(int sum) {
if (sum < 3) {
return;
}
int small = 1;
int big = 2;
int middle = (1 + sum) / 2;
int curSum = small + big;
while (small < middle) {
if (curSum == sum) {
PrintContinuousSequence(
small, big);
}
while (curSum > sum &&
small < middle) {
curSum -= small;
++small;
if (curSum == sum) {
PrintContinuousSequence(
small, big);
}
}
++big;
curSum += big;
}
}
void PrintContinuousSequence(
int small,
int big) {
for (int i = small;
i <= big;
++i) {
printf(\"%d \", i);
}
printf(\"\\n\");
}这段源码与旧页模板不同。作者在curSum等于目标后只打印，不立刻收缩；当前外层末尾仍让big加1。扩张后和通常变大，下一轮内层while再连续移动small，并可能在收缩途中打印另一个答案。
手算目标15的三个命中
初始窗口1到2，和3。外层依次把big扩到3、4、5，窗口和成为6、10、15；下一轮开头打印1到5。
随后big扩到6，和21。内层依次减1、2、3，small变4且和回到15，于是收缩途中打印4到6。
再扩到7，和22；减4、5后窗口6到7和13。扩到8后和21；下一轮减6得到15，打印7到8。
之后继续移动，直到small到达middle。三个序列按起点1、4、7递增输出。
为什么↡
循环不变式是small和big始终界定一个至少两个数的连续正整数窗口，curSum准确等于该窗口总和。
curSum小于s时，固定small再缩小右端只会让和更小；要达到目标只能扩张big。curSum大于s时，固定big再扩大左侧范围只会更大；要降低只能移除small。
每次移动都排除了不可能的窗口边界，而且small、big从不回退。任意合法窗口最终会成为当前窗口并在外层检查或内层收缩检查中被打印。
作者在内层每减一次small后立即检查相等，不能等全部收缩完才检查；否则可能跨过恰好等于s的中间窗口。
返回区间比直接打印更易测试
作者函数以printf为输出副作用，没有返回值。应用代码通常先返回端点区间，再由展示层决定展开数字或格式化。
#include <cstdint>
#include <utility>
#include <vector>
std::vector<std::pair<
std::int64_t, std::int64_t>>
findContinuousSequences(
std::int64_t target) {
std::vector<std::pair<
std::int64_t, std::int64_t>> result;
if (target < 3) {
return result;
}
std::int64_t small = 1;
std::int64_t big = 2;
std::int64_t current = 3;
const std::int64_t middle =
(target + 1) / 2;
while (small < middle) {
if (current == target) {
result.emplace_back(small, big);
}
while (current > target &&
small < middle) {
current -= small;
++small;
if (current == target) {
result.emplace_back(
small, big);
}
}
++big;
current += big;
}
return result;
}返回端点对每个答案只占O(1)空间；调用方需要具体数字时再生成small到big。若直接把每个序列全部展开，存储与打印成本取决于答案总长度。
设K为所有输出序列包含的数字总数，这个随答案变化、无法被算法内部省略的数量称为。搜索和输出成本可分开写为：
收集端点时额外空间是O(r)，r为序列数量；展开全部数字则是O(K)。忽略输出规模会低估“打印所有答案”的真实成本。
int溢出与终止中点
源码middle使用1加sum后除2。sum等于INT_MAX时，1加sum先溢出；curSum在big持续增长时也可能溢出。现代版使用int64_t，但若目标本身接近int64上限，target加1仍需用差值写法或更宽中间类型。
可将middle写成target除2加target模2，避免直接加1。窗口和也可在加big前检查是否超过类型上限。
作者while条件small小于middle，保证序列至少两项。若写成小于等于，奇数target可能把单元素target本身或超界窗口纳入检查，改变题意。
| 维度 | 作者契约或实现 | 结论 | 边界 |
|---|---|---|---|
| 输入 | 正整数 s | s 小于 3 无解 | 最小序列 1+2 |
| 序列元素 | 连续正整数 | 从 1 开始搜索 | 不含 0 和负数 |
| 序列长度 | 至少 2 | small 小于 middle | 单元素 s 不输出 |
| 结果数量 | 打印全部序列 | 不在首次命中停止 | 输出顺序按起点递增 |
| 整数类型 | 源码使用 int | 小输入正常 | 大 s 的 1+s 与窗口和可溢出 |
| 复杂度 | 双指针单向移动 | O(s) 搜索 | 打印成本另计 |
数学枚举是另一条验证路径
由二倍目标等于L乘2a加L减1，可以枚举长度L，从2开始；若二倍目标能被L整除，解出a并检查a为正整数。
#include <cstdint>
#include <utility>
#include <vector>
std::vector<std::pair<
std::int64_t, std::int64_t>>
findByLength(std::int64_t target) {
std::vector<std::pair<
std::int64_t, std::int64_t>> result;
const std::int64_t twice =
target * 2;
for (std::int64_t length = 2;
length * (length + 1)
<= twice;
++length) {
if (twice % length != 0) {
continue;
}
const std::int64_t numerator =
twice / length
- length + 1;
if (numerator > 0 &&
numerator % 2 == 0) {
const std::int64_t start =
numerator / 2;
result.emplace_back(
start,
start + length - 1);
}
}
return result;
}这版按长度而非起点生成，输出顺序可能不同，且target乘2、length平方都要防溢出。它适合作为独立参考与数学解释，不是作者实现。
长度枚举不仅要求二倍目标能被length整除，还要求二倍目标除以length再减length加1后为正偶数；为偶数才能除以2得到整数起点，为正才能保证序列从正整数开始。只检查整除会误收起点为半整数或非正数的候选。
最小起点为1时，长度L的最小和是1到L之和。随着L增长，这个最小和按平方量级增加，所以候选长度只需检查到约根号二倍目标，而不是一直到target。长度法可用较少候选直接定位区间；作者窗口法则按small和big单调移动，控制流更直观，也天然按起点排序。
连续正整数表示还与目标的奇偶因子有关：奇数长度以整数中点对称，偶数长度的平均数是半整数。某些目标没有任何长度满足整除与奇偶条件，例如4；这解释了为什么窗口会走完却不打印，而不是实现漏解。自动测试同时使用窗口与长度法对拍，可以让两种独立推导互相检验。
作者6个演示输入
作者Test函数只打印标题并调用FindContinuousSequence，没有expected参数，也不判断Passed或Failed。因此以下是预期展示，不是源码自动断言：
- sum为1，小于3，输出为空。
- sum为3，输出1到2。
- sum为4，没有至少两项连续正整数解。
- sum为9，输出2到4和4到5。
- sum为15，输出1到5、4到6、7到8。
- sum为100，输出9到16和18到22。
要自动化测试，应让核心函数返回端点，再比较集合；不要依赖捕获printf文本中的空格和换行。
#include <cassert>
#include <utility>
#include <vector>
void testContinuousSequences() {
using Pair =
std::pair<std::int64_t,
std::int64_t>;
assert(findContinuousSequences(1)
.empty());
assert(findContinuousSequences(3)
== std::vector<Pair>{{1, 2}});
assert(findContinuousSequences(4)
.empty());
assert(findContinuousSequences(9)
== std::vector<Pair>{
{2, 4}, {4, 5}});
assert(findContinuousSequences(15)
== std::vector<Pair>{
{1, 5},
{4, 6},
{7, 8}});
assert(findContinuousSequences(100)
== std::vector<Pair>{
{9, 16},
{18, 22}});
}每个返回区间还应检查起点为正、终点大于起点、等差求和确实等于target。随机小目标可与二重枚举或长度公式版对拍。
输出顺序与重复
small只向右移动，所以作者按起点递增打印。每个起点在窗口中只经过一次，不会重复输出同一端点对。
不同序列可以共享数字，例如sum为9的2到4与4到5都包含4，这不构成重复答案。题目按完整区间区分序列，不要求各结果互斥。
若目标很大，输出数字本身可能很多。日志接口还需考虑限流、取消与背压；核心搜索返回惰性端点迭代器可避免一次构建所有展开序列。
本章练习
练习
问题 1： small/big 窗口为什么不会漏解？
问题 2： 窗口上界为什么是 (s+1)/2 而不是 s？
问题 3： 手算 s=15 的三个解分别是什么？
概念说明
本章核心概念包括：正数保证单调移动。理解这些概念是掌握解题方法的关键，需要结合具体示例与边界条件反复练习。
本章回顾
- 和为s的连续正数序列可由small和big两个指针维护。
- 窗口和只在边界移动时加big或减small，无需重复求和。
- 正数保证单调移动：扩张增和、收缩减和。
- 作者命中后先打印并继续扩张，不是立即收缩模板。
- small小于middle保证每组至少两个数，sum小于3直接返回。
- 搜索O(s)，打印所有数字还要加输出规模O(K)。
- 源码int可能在中点和窗口和处溢出，现代版应整体提升类型。
- 作者6个Test只打印演示，没有自动验证期望结果。
名词解释
名词解释
本章出现的专业名词，用大白话再讲一遍。
- 滑动窗口
- 由 small 和 big 维护的连续正整数区间，通过扩张/收缩保持和为 s。
- 等差序列
- 相邻项差恒定的数列，连续正整数序列是公差为 1 的等差序列。
- 单调性
- 窗口和随扩张增大、随收缩减小，保证移动方向唯一、不漏解。