LeetCode 剑指 Offer 57 - II. 和为s的连续正数序列

约 5 分钟
文章信息 13 个分类 4 个标签
分类
LeetCode CodeTop 简单 未解决 10-20 剑指 Offer 剑指 Offer（第 2 版） 腾讯 字节 华为 美团 拼多多 百度
标签
数学 双指针 枚举 子数组问题

题目描述

✅ 剑指 Offer 57 - II. 和为s的连续正数序列

image-20261001230752585

题意分析

给定正整数 target，找出所有和等于它的连续正整数序列。每个序列至少包含两个数，数值逐个加一，不能跳过中间的数，也不能包含零或负数。

要返回每个序列的完整内容，并按序列起点从小到大排列。只返回方案数量不够；将 target 自身作为一个单元素序列也不符合要求。连续性意味着只要确定左右端点，这个序列及其和就完全确定。

解法：滑动窗口

核心思路

[!blue]

用闭区间 [left, right] 表示当前连续序列，用 sum 保存其中所有整数的和。初始选择最小的两个正整数，令 left = 1、right = 2、sum = 3。窗口至少有两个数时，才可能成为答案。

由于所有数都是正数，右端加入一个新数会使和增大，左端移走一个旧数会使和减小。若当前和小于目标，保持左端再缩短右侧只会更小，必须向右扩张。若当前和大于目标，保持左端再扩张只会更大，当前左端已经没有可行机会，应移除左端并继续找。

右端无需回退：此前因为和不足而放弃的更短右端，在左端向右移动后，窗口和只会进一步减小，不可能重新成为答案。

相等时先记录当前序列，再收缩左端。对于同一个左端，右端继续增大后总和会严格增加，不会再次等于目标，因此记录后直接寻找更大的左端不会漏解。两个端点都只向右移动，每个候选区间最多记录一次，答案的起点顺序也自然递增。

每次移动还要同步维护 sum：收缩时先减掉旧的 left，再增加左端；扩张时先增加 right，再加上新进入的数。这样 sum 始终精确对应当前闭区间。

当窗口缩到只剩一个数时即可结束。缩小前最后一个双元素窗口的和已经不小于目标，而后面从更大起点开始、至少包含两个数的窗口只会更大，不可能再产生答案。left < right 因此既排除了单元素结果，也给出了搜索终点。

解题步骤

  1. 初始化 left = 1、right = 2、sum = 3，结果列表为空。
  2. 在 left < right 时比较当前窗口和与目标。
  3. 若和恰好相等，创建长度为 right - left + 1 的结果数组，依次写入左右端点之间的整数。
  4. 若 sum >= target，先减去旧左端，再令 left++；命中答案后也走这一分支。
  5. 若 sum < target，先令 right++，再把新右端加到窗口和中。
  6. 循环结束后返回已按起点递增排列的全部序列。

代码实现

class Solution {
    public int[][] findContinuousSequence(int target) {
        List<int[]> result = new ArrayList<>();
        int left = 1;
        int right = 2;
        int sum = 3;

        while (left < right) {
            if (sum == target) {
                int[] sequence = new int[right - left + 1];

                for (int i = 0; i < sequence.length; i++) {
                    sequence[i] = left + i;
                }

                result.add(sequence);
            }

            if (sum >= target) {
                // 先减去旧左端，再移动窗口，命中答案后也必须继续收缩。
                sum -= left;
                left++;
            } else {
                right++;
                // 右端已先移动，这里加入的是新进入窗口的数。
                sum += right;
            }
        }

        return result.toArray(new int[0][]);
    }
}

func findContinuousSequence(target int) [][]int {
    result := make([][]int, 0)
    left, right, sum := 1, 2, 3

    for left < right {
        if sum == target {
            sequence := make([]int, right-left+1)
            for i := range sequence {
                sequence[i] = left + i
            }
            result = append(result, sequence)
        }

        if sum >= target {
            // 先减去旧左端，再移动窗口，命中答案后也必须继续收缩。
            sum -= left
            left++
        } else {
            right++
            // 右端已先移动，这里加入的是新进入窗口的数。
            sum += right
        }
    }
    return result
}

复杂度分析

  • 时间复杂度：O(target + S)，其中 S 为所有返回序列的元素总数。两个端点都只向右移动，搜索次数为 O(target)；输出完整序列还需要逐个写入 S 个元素。
  • 空间复杂度：结果占 O(S)。搜索本身只保存常数个变量；若返回 r 个序列，Java 在转换结果数组前还保留 O(r + 1) 个临时列表引用，Go 不计返回结果时为 O(1)。

关键点总结

[!green]

  • 正数保证两种指针移动对窗口和的影响方向确定，才能根据大小关系排除不可能的区间。
  • 窗口采用闭区间，和的增减与端点更新必须对应同一批元素。
  • 命中后继续收缩即可找全答案，起点递增使结果无需额外排序。
  • 返回的是具体序列，复杂度中需要计入生成所有结果元素的开销。

易错点总结

[!yellow]

  • 命中后只记录不移动：下一轮会停留在同一个窗口，导致重复记录或死循环。
  • 先移动左端再减它的值：减掉的会是新左端而非移出的旧元素，使 sum 与窗口脱节。
  • 扩张时先加旧右端：新进入窗口的应是 right + 1，先移动后累加才与实现一致。
  • 允许 left == right 作为结果：题目至少要求两个数，单独一个目标值不合法。
  • 只把端点存入答案：需要输出整个连续序列，而不是返回一个二元区间。
  • 把这一移动规则直接用于含负数的数组：加入或删除负数会破坏和的单调变化，本题的正确性依赖所有数为正。

相似题目

题目 难度 关联与区别
829. 连续整数求和 困难 原题允许单项target并只统计数量，本题每段至少两个数且输出具体序列。
209. 长度最小的子数组 中等 正整数让窗口和随两端移动单调，本题找全部精确和区间，原题找达到下界的最短长度。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/60890574
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！