题⽬描述

⼩明很喜欢数学，有⼀天他在做数学作业时，要求计算出 9~16 的和，他⻢上就写出了正确答案是 100 。但是他并不满⾜于此，他在想究竟有多少种连续的正数序列的和为 100 (⾄少包括两个数)。没多久，他就得到另⼀组连续正数和为 100 的序列: 18,19,20,21,22 。现在把问题交给你，你能不能也很快的找出所有和为S的连续正数序列? Good Luck!

返回值描述：输出所有和为 S 的连续正数序列。序列内按照从⼩⾄⼤的顺序，序列间按照开始数字从⼩到⼤的顺序

示例1：

输⼊：9 返回值：[[2,3,4],[4,5]]

思路及解答

暴力枚举

通过双重循环尝试所有可能的序列起点和终点。

针对每⼀个索引起点，都计算后续的连续⼦数组的和，并且将元素存到临时 list 中。

如果和不超过 sum ,那么就继续往后⾯遍历；

如果和等于 sum，则说明该连续⼦数组满⾜条件，将临时 list 添加到结果集中

如果和⼤于 sum，则说明连续⼦数组已经超过，该索引起点的不满⾜条件，直接 break 。

注意的是，起点我们只需要遍历到 sum/2 的位置即可，因为⼤于 sum/2 的索引，任何两个数的和都⼤于 sum，不符合条件。

  • 时间复杂度：O(n²)

  • 空间复杂度：O(k)，k为结果序列数

数学计算

利用等差数列求和公式进行数学优化，减少计算量。

通常我们遇到连续序列求和，是知道首项和项数去求总和；而这里我们是已知总和 S，反推是否存在合法的“首项”和“项数”。

假设我们要找的连续正数序列的首项为 x，序列长度（即包含的数字个数）为 n 。 因为是连续正数，这个序列可以表示为： x,x+1,x+2,…,x+(n−1)x,x+1,x+2,…,x+(n−1)

这是一个公差 d=1d=1 的等差数列。根据等差数列求和公式：n*(首项 + 末项)/2 = S；代入变量，就是S = n*(x + x+(n−1))/2 = n*(2x+n-1)/2

我们的目标是已知 SS，求 xx 和 nn 。我们将上述公式变形，把 xx 作为未知数解出来：

  1. 两边同乘 2：2S=n(2x+n−1)

  2. 两边除以 n ： 2S/n = 2x+n−1

  3. 移项：2x=2S/n − n + 1

  4. 通分整理（为了避免浮点数运算，代码中采用了通分的形式）：x=(2S−n(n−1)) / 2n

  • 分子：2 * S - n * (n - 1)

  • 分母：2 * n

知道了上面步骤，我们就可以通过枚举n来完成结果推导

为什么枚举 nn 而不是枚举 xx ？我们需要确定循环的边界：

  • 因为题目要求至少包含两个数，所以 n 从 2 开始。

  • n 的最大值是多少？

    • 当首项 x 取最小值 1 时，序列的和最小。此时序列为 1,2,3,…,n

    • 其和为 n(n+1)/2

    • 如果连最小的和都超过了 S，那么更大的 n 肯定也不成立。

    • 因此循环条件是： n(n+1)/2 ≤ S

  • 时间复杂度：O(n)

  • 空间复杂度：O(1)

滑动窗口（推荐）

以上的方法更像是捷径，用双指针更像是我们做算法的初衷。但在实际工程落地时，还是什么好，什么方便用什么。

使用双指针技术，动态调整窗口大小。通过维护一个动态的区间 [left, right]样在正数序列上滑动，通过不断调整窗口的左右边界来“凑”出目标和 sum。

想象你有一个可以伸缩的框，框住了一串连续的正整数。

  • left 是框的左边缘，right 是框的右边缘。

  • currentSum 始终记录着当前框内所有数字的和。我们的目标就是移动这个框，让框里的数字之和恰好等于 sum。

当前状态判断条件动作逻辑解释和太小currentSum < sum扩大窗口：right++说明框里的数加起来还不够，需要把右边缘向右扩，纳入更大的数进来。和太大currentSum > sum缩小窗口：left++说明框里的数加超了，需要把左边缘向右缩，踢掉最小的那个数。刚好相等currentSum == sum记录并收缩找到了一个合法序列！把它存入结果集。为了寻找下一个可能的序列，我们必须破坏当前的平衡，将左边缘右移（left++），继续尝试。

  • 时间复杂度：O(n）

  • 空间复杂度：O(1)

为什么不会漏掉解？很多同学可能会担心：“当和太大的时候，只移动 left 而不重置 right，会不会错过某些以较小数字开头的序列？”

答案是不会。我们可以这样理解：

假设当前窗口是 [1, 2, ..., 8]，和小于 target；当我们把 right 移到 9 时，[1, 2, ..., 9] 的和突然大于 target 了。这说明以 1 开头的序列不可能有解了。 接下来我们要找以 2 开头的序列。因为 2 + ... + 8 的和一定小于 1 + 2 + ... + 8（也就是一定小于 target），所以以 2 开头的序列，其右边界至少也要延伸到 9 甚至更右。 因此，我们完全不需要把 right 拉回到 2 重新开始，直接在上一轮 right 的位置继续向右试探即可。这种“不回退”的特性保证了每个数字最多被 left 和 right 各访问一次，时间复杂度稳定在 O(S) 。