题目
输入一个正数s,打印出所有和为s的连续正数序列(至少含有两个数)。
例如输入15,由于1+2+3+4+5=4+5+6=7+8=15,所以结果打印出3个连续序列1~5、4~6和7~8。
样例
输入:15
输出:[[1,2,3,4,5],[4,5,6],[7,8]]
解法:双指针
- 设置两个指针i和j,分别指向连续正数序列的起始和终止
- 用s表示当前连续正数序列的和,即s=i+(i+1)+…+js=i+(i+1)+…+j
- 以i递增的方式遍历整个序列(1到n),代表查找以i开头的时候结尾j应该是多少。当s
sum说明向后走即可。 - 注意上述遍历过程中,s=sum的情况下不需要把j往前移动,原因是当进入下一个循环前s−=i,即(i+1)到j的和肯定小于sum。
时间复杂度O(n),空间复杂度O(n2)
class Solution {
public:
vector<vector<int> > findContinuousSequence(int sum) {
vector<vector<int>> ans;
for (int i = 1, j = 1, s = 1; i < sum; i++) {
while (s < sum) j++, s += j;
if (sum == s && i < j) {
vector<int> t;
for (int k = i; k <= j; k++)
t.push_back(k);
ans.push_back(t);
}
s -= i;
}
return ans;
}
};