牛客网3690题：滑动窗口法解决连续正数序列和问题

引言

在编程面试和算法学习中，连续子序列和问题是一类常见且重要的问题。今天我们将深入探讨牛客网3690题如何使用滑动窗口法（也称为双指针法）高效解决"找出所有和为S的连续正数序列"这一问题。这种方法不仅时间复杂度为O(n)，而且思路清晰，代码简洁，非常适合算法初学者掌握。

一、问题理解

给定一个正整数S，我们需要找出所有连续的正整数序列，这些序列的和恰好等于S。例如，当S=100时，有两个解：

1. 9+10+11+12+13+14+15+16 = 100

2. 18+19+20+21+22 = 100

问题特点

• 序列至少包含两个数

• 序列必须是连续的正整数

• 需要找出所有可能的序列

二、暴力解法与优化思路

最直观的方法是使用双重循环枚举所有可能的序列起点和终点，计算它们的和。这种方法时间复杂度为O(n²)，在n较大时效率很低。

我们可以观察到连续正数序列的和具有以下性质：

1. 序列越长，起始数字越小

2. 序列的和可以用等差数列求和公式计算：(首项+末项)*项数/2

3. 当序列起始数字超过S/2时，至少需要两个数，和必然大于S

基于这些观察，我们可以设计更高效的算法。

三、滑动窗口法详解

滑动窗口法是一种通过维护一个动态变化的窗口来解决问题的技巧。对于本问题：

1. 窗口定义：用两个指针small和big表示窗口的左右边界，初始时都指向1和2

2. 当前和计算：维护currentSum表示窗口内数字的和

3. 窗口移动规则：

• currentSum == sum：找到解，记录结果，然后移动左边界

• currentSum < sum：和不足，移动右边界扩大窗口

• currentSum > sum：和过大，移动左边界缩小窗口

关键点分析

1. 终止条件：small只需要移动到(sum+1)/2即可，因为至少两个数

2. 时间复杂度：每个元素最多被访问两次（被big和small各访问一次），所以是O(n)

3. 空间复杂度：除结果外只使用了常数空间，是O(1)

四、代码实现解析

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param sum int整型
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > FindContinuousSequence(int sum) {
        vector<vector<int>> result; // 存储所有结果序列
        if (sum < 3) return result; // 至少需要两个数，最小和为1+2=3

        int small = 1;  // 窗口左边界
        int big = 2;    // 窗口右边界
        int currentSum = small + big; // 当前窗口内数字的和

        // 窗口滑动终止条件：small超过sum的一半
        // 因为至少两个数，small最大为(sum+1)/2
        int middle = (sum + 1) / 2;

        while (small < middle) {
            if (currentSum == sum) {
                // 找到符合条件的序列，保存结果
                vector<int> sequence;
                for (int i = small; i <= big; ++i) {
                    sequence.push_back(i);
                }
                result.push_back(sequence);

                // 继续寻找其他可能序列
                currentSum -= small;
                small++;
            } else if (currentSum < sum) {
                // 和不足，扩大窗口右边界
                big++;
                currentSum += big;
            } else {
                // 和过大，缩小窗口左边界
                currentSum -= small;
                small++;
            }
        }

        return result;
    }
};

五、实际应用示例

以sum=15为例，看看算法如何工作：

1. [1,2,3,4,5] → 和=15 → 记录

2. [4,5,6] → 和=15 → 记录

3. [7,8] → 和=15 → 记录

4. [15] → 不满足至少两个数 → 结束

最终得到三个解：[1,2,3,4,5], [4,5,6], [7,8]

六、常见错误与调试技巧

1. 边界条件处理：特别注意sum小于3的情况

2. 死循环：确保窗口一定会移动，避免small和big停滞

3. 结果顺序：题目要求结果按起始数字排序

七、总结

滑动窗口法是解决连续子序列问题的利器，通过维护一个动态变化的窗口，我们能够高效地找到所有解。这种方法不仅适用于本题，还可以应用于许多类似的子数组/子序列问题。掌握滑动窗口法的核心思想，能够帮助你在算法学习和编程面试中解决更多复杂问题。