输入一个正整数 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;
}
};