和为S的连续正数序列

---

题目描述

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

输出描述：

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

解题思路

• 通过两个指针，分别指向最低位和最高位。
• 通过 (a + b) * n / 2求和公式的到两指针间的和；
• 若当前和 小于 指定和S，则最高位指针向左移动一位；
• 若当前和 大于 指定和S， 则最低位指针向左移动一位；
• 若当前和 等于 指定和S， 则最高位和最低位之间的数组即为所求的连续序列之一；
• 如上循环，求出所有序列。知道最低位指针 大于 最高位指针，循环结束。

代码

class Solution
{
public:
    vector<vector<int>> FindContinuousSequence(int sum)
    {
        vector<vector<int>> result;
        
        // 定义最高位和最低为的指向值，由于题中说是正整数序列，且要求至少包括两个连续的数，故有如下定义
        int phigh = 2, plow = 1;
        
        // 循环
        while (plow < phigh)
        {
            int currsum = (plow + phigh) * (phigh - plow + 1) >> 1; // 别忘了 +1，
            if (currsum < sum)
                phigh++;
            if (currsum == sum)
            {
                vector<int> temp;
                for (int i = plow; i <= phigh; i++)
                {
                    temp.push_back(i);
                }
                result.push_back(temp);
                plow++; // 继续对剩下的序列进行查找
            }
            if (currsum > sum)
                plow++;
        }
        
        return result;
    }
};

参考博文链接：https://cuijiahua.com/blog/2018/01/basis_41.html