题目的主要信息：

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

总结题意，就是给定一个1到sum的序列，求所有和为sum的连续序列。

方法一：

暴力枚举。枚举一遍所有起点可能长度的序列，由题可知序列至少两个数，因此每次序列的起点最多为sum/2。计算当前序列之和，如果序列之和等于sum，则保存该序列到到res中，如果序列之和大于sum，结束该起点的遍历，因为后面的序列之和必定比当前序列大，即都会大于sum。枚举完所有序列后，res中即为所有he为sum的连续正数序列。 具体做法：

class Solution {
public:
 vector<vector<int> > FindContinuousSequence(int sum) {
     vector<vector<int>> res;
     for (int i=1; i<=sum/2; ++i) { 
         for (int j=i+1; j<sum; ++j) {//遍历所有可能的序列
             int tmp = 0;
             for (int k = i; k<=j; ++k) {//计算序列之和
                 tmp += k;
             }
             if (sum == tmp) {//如果该序列之和等于tmp
                 vector<int> ans;
                 for (int k=i; k<=j; ++k){
                     ans.push_back(k);
                 }
                 res.push_back(ans);//保存该序列
             }else if (tmp > sum) {//如果该序列之和大于sum，j不用往下遍历了
                 break;
             }
         }
     }
     return res;
 }
};

复杂度分析：

• 时间复杂度：$O(n^3)O(n^3)$，三重for循环。
• 空间复杂度：$O(n)O(n)$，最坏情况下，ans中储存n个数字。

方法二：

优化方法一。方法一每枚举一个序列都要遍历求和，但是我们知道，i到j的和等于i到j-1的和加上j的值，因此计算每个序列的和只需要在上一个计算的序列和中加上新增的值，可以大大减少时间复杂度。如果序列之和等于sum，则保存该序列到到res中，如果序列之和大于sum，结束该起点的遍历，因为后面的序列之和必定比当前序列大，即都会大于sum。枚举完所有序列后，res中即为所有he为sum的连续正数序列。

具体做法：

class Solution {
public:
    vector<vector<int> > FindContinuousSequence(int sum) {
        vector<vector<int>> res;
        int tmp = 0;
        for (int i=1; i<=sum/2; ++i) {//枚举所有序列
            for (int j=i; j<sum; ++j) {
                tmp += j;//i到j的和等于i到j-1的和加上j的值
                if (sum == tmp) {
                    vector<int> ans;
                    for (int k=i; k<=j; ++k){//保存该序列
                        ans.push_back(k);
                    }
                    res.push_back(ans);
                }else if (tmp > sum) {//结束从i开始的序列枚举
                    tmp = 0;
                    break;
                }
            }
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：$O(n^2)O(n^2)$，两重for循环。
• 空间复杂度：$O(n)O(n)$，最坏情况下，ans中储存n个数字。