CS-Notes 剑指 Offer 57.2 详解用双指针滑动窗口找出所有和为 S 的连续正数序列【免费下载链接】CS-Notes:books: 技术面试必备基础知识、Leetcode、计算机操作系统、计算机网络、系统设计项目地址: https://gitcode.com/GitHub_Trending/cs/CS-Notes本篇围绕 CS-Notes 剑指 Offer 题解中的 57.2 和为 S 的连续正数序列 展开完整讲解这道经典面试题的题意、基于双指针滑动窗口的参考实现、每一步的循环不变量与边界条件并补充 O(√S) 的数学解法作为对照。读完你可以掌握如何在 O(S) 时间内枚举全部满足条件的连续正整数序列为什么该解法天然不会漏解、也不会输出单元素序列以及它与 57.1 和为 S 的两个数字 中静态双指针的本质区别。一、题目描述与示例题目要求输出所有和为 S 的连续正数序列。原文档给出的示例和为 100 的连续正数序列有两个——[9, 10, 11, 12, 13, 14, 15, 16] [18, 19, 20, 21, 22]可以先验证一下这两个序列前者是首项 9、末项 16 的 8 项等差数列和为 (9 16) × 8 / 2 100后者是首项 18、末项 22 的 5 项等差数列和为 (18 22) × 5 / 2 100。除这两组之外没有其他解——这一点可以用数学解法见本文第四节快速枚举验证。这道题在仓库的 剑指 Offer 题解 - 目录 中被归入双指针章节与 57.1、58.1、58.2 并列说明出题人期望的正是指针移动类解法而非暴力枚举。二、解题思路把窗口当成可伸缩的序列与 57.1 和为 S 的两个数字 中一左一右对向扫描固定数组不同本题没有现成数组扫描的对象是自然数列 1, 2, 3, …本身。核心思想是维护一个左右边界都指向正整数的滑动窗口 [start, end]窗口当前和curSum sum说明要凑出更大的和只能扩大窗口end并把新的end加入curSum窗口当前和curSum sum说明和超了只能收缩窗口curSum - start并start窗口当前和curSum sum命中一个解记录[start, end]然后滑动窗口左边界右移、右边界再右移一格继续寻找后续解。这里有一个关键前提保证了算法的正确性序列中所有元素都是正数因此扩大窗口必然使和严格增大、收缩窗口必然使和严格减小。窗口和的变化方向是确定单调的两个指针永远不会来回横跳每个整数至多进入窗口一次这为 O(S) 的总复杂度奠定了基础。同时由于窗口初始为[1, 2]且左边界右移时右边界始终至少右移一格任何时刻窗口内至少包含两个数收缩过程中允许退化为单个元素start end但此时和等于窗口和只有当该数恰好等于 S 才可能误判见第三节的终止条件分析。这也符合题意对序列的隐含要求——至少两个连续正整数。三、参考实现逐步解析仓库中的原始解法如下来自 57.2 和为 S 的连续正数序列public ArrayListArrayListInteger FindContinuousSequence(int sum) { ArrayListArrayListInteger ret new ArrayList(); int start 1, end 2; int curSum 3; while (end sum) { if (curSum sum) { curSum - start; start; } else if (curSum sum) { end; curSum end; } else { ArrayListInteger list new ArrayList(); for (int i start; i end; i) list.add(i); ret.add(list); curSum - start; start; end; curSum end; } } return ret; }逐段拆解1. 初始状态窗口[1, 2]curSum 3。选择从最小窗口起步是因为更小的窗口和无法达到 S除单元素外[1, 2]就是最小的连续正数序列从最小窗口开始向右生长可以按首项从小到大的顺序自然产出所有解。2.curSum sum分支收缩左边界。注意收缩后curSum只减去了start一个元素窗口变为[start1, end]和的变化与窗口变化严格同步。3.curSum sum分支扩张右边界。end之后把新纳入窗口的end累加进curSum窗口变为[start, end]。4.curSum sum分支记录解并整体滑动。先把[start, end]逐个填入结果再执行curSum - start; start; end; curSum end;——等价于丢弃左端元素、右端再纳入一个新元素窗口变为[start1, end1]。这一步很关键命中解之后不能原地不动会死循环也不能只缩不扩会跳过end1可能参与的新解整体右滑一格保证窗口连续向前扫描、不遗漏。5. 循环条件while (end sum)天然的终止器。右边界从 2 开始每轮至多加 1最多推进到sum - 1。这个看似随意的条件实际上同时承担了两个职责避免无意义的扩张一旦end达到sum窗口内任何包含sum本身的组合其和必然 ≥ sum 且窗口至少两个元素和必然超过 S不可能再有解杜绝单元素序列被输出当窗口退化为单元素[k]且k sum时恰好对应end sum此时循环条件已不成立else分支不可能执行因此永远不会把[S]这种单元素序列混入答案。边界输入sum 1时初始end 2已经不满足end sum循环体一次都不执行返回空列表语义正确最小的两元素连续序列[1, 2]的和已经是 3sum 2同理返回空。用 S 15 走一遍主流程这是最能暴露各分支协作方式的小样例步骤窗口curSum动作1[1, 2]3 15扩张 → [1, 3]2[1, 3]6 15扩张 → [1, 4]3[1, 4]10 15扩张 → [1, 5]4[1, 5]15 15记录[1,2,3,4,5]整体右滑 → [2, 6]5[2, 6]20 15收缩 → [3, 6]18→ 收缩 → [4, 6]6[4, 6]15 15记录[4,5,6]整体右滑 → [5, 7]7[5, 7]18 15收缩 → [6, 7]13 15扩张 → [6, 8]21 15收缩 → [7, 8]8[7, 8]15 15记录[7,8]右滑 → [8, 9]179[8, 9]17收缩 → [9]9→ 扩张、收缩交替窗口在单元素与两元素间震荡10end 推进至 15—end sum不再成立循环结束最终输出[1,2,3,4,5]、[4,5,6]、[7,8]三个序列且按首项升序排列——这与题目对 100 的输出顺序[9,...]在前、[18,...]在后一致属于滑动窗口解法的自然副产品。四、复杂度与 O(√S) 数学解法对照滑动窗口法复杂度end是只增不减的指针从 2 推进到不超过sum - 1循环总轮数为 O(S)每轮除记录解外均为 O(1) 操作记录所有解的总开销与解的总长度同阶。因此时间复杂度 O(S)额外空间复杂度 O(1)不计输出容器。面试中这一点几乎必问而答案的支撑正是end单调、元素至多入窗一次这一不变量。数学法对照思路设序列长度为 n、首项为 a则 n 项等差数列求和给出a·n n(n-1)/2 S即a (S - n(n-1)/2) / n。由于 a ≥ 1有n(n1)/2 ≤ S因此 n 的上界约为 √(2S)。只需枚举 n检查S - n(n-1)/2是否为正的且能被 n 整除public ArrayListArrayListInteger findByMath(int sum) { ArrayListArrayListInteger ret new ArrayList(); for (int n (int) Math.sqrt(2 * (long) sum); n 2; n--) { long rest sum - (long) n * (n - 1) / 2; if (rest 0 rest % n 0) { int start (int) (rest / n); ArrayListInteger list new ArrayList(); for (int i 0; i n; i) list.add(start i); ret.add(list); } } return ret; }n 从大到小枚举时首项 a 恰好从小到大输出顺序与滑动窗口法一致。时间复杂度为 O(√S) 加上记录解的开销理论上更快但滑动窗口法只需一次线性扫描、实现上更直观且更容易推广到和为 S 的连续子序列数组元素未必从 1 开始这类变体这也是仓库把它放在双指针章节的原因。五、与 57.1 双指针的对比及易错点在 剑指 Offer 题解 - 目录 的双指针分类下57.1 与 57.2 恰好构成一组对照57.1静态双指针数组已给定且有序两个指针从两端对向逼近每次只比较当前两端元素的和与 target 的大小时间 O(n)空间 O(1)57.2滑动窗口对象是隐含的无限自然数列两个指针同向向右推进窗口长度动态伸缩时间 O(S)空间 O(1)。两者的共同本质是利用序列的单调性让当前和与目标的偏差唯一决定下一步指针移动方向从而避免枚举所有起点和终点组合的 O(S²) 暴力做法。实践中的几个易错点命中解后的滑动方向。只执行start而不end会漏掉右端新元素参与的新解两者都不动则会死循环。仓库实现中左移一格、右移一格的组合是刻意设计的。循环上界。写成while (end sum)不会改变结果end sum时curSum sum恰好对应单元素窗口但按前文分析此时循环已不应进入而漏掉上界直接while (true)则会导致死循环end sum是该解法的安全阀。相邻题的代码细节。顺带提醒仓库中 57.1 和为 S 的两个数字 的示例代码里有一处笔误——int cur nums[i] array[j];中的array未定义应为nums[j]移植该解法时注意修正避免误以为是57.2特有的问题。六、小结题目输出所有和为 S 的连续正数序列仓库参考解法见 57.2 和为 S 的连续正数序列主解法为双指针滑动窗口curSum小于目标就扩右界、大于目标就缩左界、等于目标就记录并整体右滑end sum作为终止条件同时防止无效扩张与单元素解复杂度时间 O(S)、额外空间 O(1)追求更优可用等差求和公式枚举长度 n做到 O(√S)与 57.1 的静态双指针对照记忆能更清晰地理解单调性决定指针移动方向这一双指针方法的通用原理更多双指针题目可参考仓库的 Leetcode 题解 - 双指针。【免费下载链接】CS-Notes:books: 技术面试必备基础知识、Leetcode、计算机操作系统、计算机网络、系统设计项目地址: https://gitcode.com/GitHub_Trending/cs/CS-Notes创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考