题目描述

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

数据范围：1000<n≤100

进阶：时间复杂度 O(n)O(n)

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

题解：滑动窗口

主要思路：序列可以看做是等差序列，其中公差为1。由等差序列公式可知等差数列和为：he=(a+b)* (b-a+1)/2。
因此本题可以采用滑动窗口来求解正数序列。
窗口左侧为a，窗口右侧为b，窗口中元素的和为he，其中窗口中的序列服从等差序列。
初始时，左侧窗口值为1，右侧窗口值为2。求解窗口中的和he，并和目标值sum进行比较，比较结果有如下三种情况：

1. 当 he>sum 时：左侧窗口a向右滑动，即元素减少一个，继续求和跟sum比较
2. 当 he==sum 时：窗口内的元素即为求解的子序列和，将窗口中的元素存放到二维数组中（每个序列存放在一维数组）。同时窗口b向右滑动，继续接收新的子序列。
3. 当 h<sum 时：右侧窗口b向右滑动，即元素增加一个，继续求和跟sum比较 循环结束边界条件： 窗口一直缩小到一个元素的时候即退出循环 (题目中序列元素最少为2个，因次a<b即为循环条件，等于的时候则退出循环，因为等于的时候窗口缩小到一个元素了)

图示来自鸠摩罗什，在此引用

代码

class Solution {
public:
    vector<vector<int> > FindContinuousSequence(int sum) {
        //双指针
        vector<vector<int>> v;
        int a = 1;//左指针
        int b = 2;//右指针
        int he = 0;
        while(a < b){
            he=(a+b)*(b-a+1)/2; //等差数列求窗口值的和
            if(he == sum){
                vector<int> temp;
                for(int i =a;i<=b;i++){
                    temp.push_back(i);
                }
                v.push_back(temp);//循环完毕，临时变量temp自动销毁
                b++;//注意：要找出所有的数组，因此次数一定要b++
            }else if(he > sum){
                a++;
            }else{
                b++;
            }
        }
        return v;
    }
};