题目的主要信息：

• 找出所有和为S的连续正数序列，序列至少包括两个数
• 序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序
• 进阶要求：时间复杂度 $O(n)O(n)$

方法一：暴力枚举

具体做法：

我们可以从数字1开始枚举从每个数开始的连续的数字，将其累加判断其是否等于目标，如果小于目标数则继续往后累加，如果大于目标数说明会超过，跳出，继续枚举下一个数字开始的情况，只有刚好累加和等于目标数才可以记录从开始到结束这一串数字，代表是一个符合的序列。

而因为序列至少两个数，每次枚举区间的起始数字最多到目标数的一半向下取整即可。

class Solution {
public:
    vector<vector<int> > FindContinuousSequence(int sum) {
        vector<vector<int> > res;
        vector<int> temp;
        int sum1 = 0;
        int up = (sum - 1) / 2; //因为序列至少两个数，因此枚举最多到该数字的一半向下取整
        for(int i = 1; i <= up; i++){ //枚举左区间
            for(int j = i; ;j++){ //从左区间往后依次连续累加
                sum1 += j;
                if(sum1 > sum){ //大于目标和则跳出该左区间
                    sum1 = 0;
                    break;
                }else if(sum1 == sum){ //等于则找到
                    sum1 = 0;
                    temp.clear();
                    for(int k = i; k <= j; k++) //记录线序的数字
                        temp.push_back(k);
                    res.push_back(temp);
                    break;
                }
            }
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：$O(n\sqrt{n})O(n\backslash sqrt\; n)$，其中$nn$为目标数字sum，外层枚举最多$\lfloor n\mathrm{/}2\rfloor \backslash lfloor\; n/2\; \backslash rfloor$次，内层判断最多不会超过$O(\sqrt{n})O(\backslash sqrt\; n)$，因为如果从1累加到$\sqrt{n}\backslash sqrt\; n$会大于$nn$，而从1累加到$\sqrt{n}-1\backslash sqrt\; n\; -1$会小于$nn$，因此最坏情况下累加$\sqrt{n}\backslash sqrt\; n$次
• 空间复杂度：$O(\sqrt{n})O(\backslash sqrt\; n)$，其中res属于返回答案必要空间，额外空间只有temp数组，最坏情况长度为$\sqrt{n}\backslash sqrt\; n$

方法二：滑动窗口

具体做法：

从某一个数字开始的连续序列和等于目标数如果有，只能有一个，于是我们可以用这个性质来使区间滑动。

两个指针l、r指向区间首和区间尾，公式$(l+r)\ast (r-l+1)\mathrm{/}2(l\; +\; r)\; *\; (r\; -\; l\; +\; 1)\; /\; 2$计算区间内部的序列和，如果这个和刚好等于目标数，说明以该区间首开始的序列找到了，记录下区间内的序列，同时左区间收缩；如果区间和大于目标数，说明该区间过长需要收缩，只能收缩左边；如果该区间和小于目标数，说明该区间过短需要扩大，只能向右扩大，移动区间尾。

class Solution {
public:
    vector<vector<int> > FindContinuousSequence(int sum) {
        vector<vector<int> > res;
        vector<int> temp;
        for(int l = 1, r = 2; l < r;){ //从1到2的区间开始
            int sum1 = (l + r) * (r - l + 1) / 2; //计算区间内的连续和
            if(sum1 == sum){ //如果区间内和等于目标数
                temp.clear();
                for(int i = l; i <= r; i++) //记录区间序列
                    temp.push_back(i);
                res.push_back(temp);
                l++; //左区间向右
            }else if(sum1 < sum) //如果区间内的序列和小于目标数，右区间扩展
                r++;
            else //如果区间内的序列和大于目标数，左区间收缩
                l++;
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，区间移动次数最多$\lfloor n\mathrm{/}2\rfloor \backslash lfloor\; n/2\; \backslash rfloor$次
• 空间复杂度：$O(\sqrt{n})O(\backslash sqrt\; n)$，其中res属于返回答案必要空间，额外空间只有temp数组，最坏情况长度为$\sqrt{n}\backslash sqrt\; n$