和为S的连续正数序列:最直观的想法是,穷举法。使用res记录结果数组,使用temp记录临时数组,使用一个变量i枚举起始区间,由于要求的是连续正数序列,且序列至少包含两个数,故起始区间最多枚举到S的一半向下取整,使用一个变量j枚举结束区间,其范围由累加和控制,使用add表示区间内的数值和,首先判断区间内的累加和与目标和的大小关系,如果累加和大于目标和则退出内层循环,反之如果累加和等于目标和则清空之前的临时数组,并且将当前区间的数值依次加入到临时数组,再退出循环,从下一个起始区间开始枚举。

vector<vector<int> > FindContinuousSequence(int sum) 
{
    // 结果数组
    vector<vector<int>> res;
    // 临时数组
    vector<int> temp;
    // 序列至少两个数 最多从该数字一半向下取整开始枚举
    int end=(sum-1)/2;
    // 枚举左区间
    for(int i=1;i<=end;i++)
    {
       // 每个区间开始记录累加和add为0
       int add=0;
       // 从左往后依次连续累加 右区间由累加和控制
       for(int j=i;;j++)
       {
           add+=j;
           // 累加和大于目标和则退出
           if(add>sum)
              break;
           // 累加和等于目标和则加入结果数组
           else if(add==sum)
           {
              // 先将之前的临时数组清空 再存储当前数组 并加入到结果数组
              temp.clear();
              // 当前区间 起始下标为i 结束下标为j
              for(int k=i;k<=j;k++)
                  temp.push_back(k);
              res.push_back(temp);
              break;
           }
        }
    }
    return res;
}

优化:上述方法是首先枚举区间起始位置和区间结束位置,然后判断区间内数值累加和是否合法,如果合法再加入到临时数组。但是,连续整数序列是可以使用等差数列求和公式的!所以,不妨使用滑动窗口,由于序列至少两个数,所以窗口左边界指向1,窗口右边界指向2,且判断条件是区间左边界小于区间右边界,然后利用公式求当前窗口内的累加和,如果等于目标和,则清空临时数组,再根据左右边界,将其区间内的数值依次加入临时数组,再将临时数组加入结果数组,接着将左区间右移,反之如果大于目标和则将左区间右移,反之如果小于目标和则将右区间右移。

// left到right且d=1的等差数列求和公式为n*(left+right)/2
int add=(left+right)*(right-left+1)/2;
vector<vector<int> > FindContinuousSequence(int sum) 
{
     // 结果数组
     vector<vector<int>> res;
     // 临时数组
     vector<int> temp;
     // left表示区间左边界 right表示区间右边界
     for(int left=1,right=2;left<right;)
     {
        // 等差数列求和公式
        int add=(left+right)*(right-left+1)/2;
        // 累加和等于目标和
        if(add==sum)
        {
            temp.clear();
            for(int i=left;i<=right;i++)
               temp.push_back(i);
            res.push_back(temp);
            // 左区间右移 开始下一轮枚举
            left++;
        }
        // 累加和小于目标和
        else if(add<sum)
           // 右区间右移
           right++;
        // 累加和大于目标和
        else
           // 左区间右移
           left++;
    }
    return res;
}