和为s的连续正数序列

输入一个正整数 target ,输出所有和为 target 的连续正整数序列(至少含有两个数)。

序列内的数字由小到大排列,不同序列按照首个数字从小到大排列。

思路:

定义两个数front,rear。front表示序列的末尾,rear表示序列的开端。初时front=2,rea=1。这是一个不断变化的序列。计算这个序列的和,如果等于target,则找到一个答案,因为可能还有其他答案,所以此时,front加一。如果大于target,rear加一。如果小于target,front加一。

代码:

class Solution {
public:
    vector<vector<int>> findContinuousSequence(int target) {
        int front = 2,rear = 1;
        vector<vector<int>> ans;
        while(rear < front) {
            int sum = (front+rear)*(front-rear+1)/2;
            if(sum == target) {
                vector<int> tmp;
                for(int i = rear;i <= front;i++) {
                    tmp.push_back(i);
                }
                ans.push_back(tmp);
                front++;
            }
            else if(sum > target) {
                rear++;
            }
            else {
                front++;
            }
        }
        return ans;
    }
};