题目描述
输入一个非负整数 S,打印出所有和为 S 的连续正数序列(至少含有两个数)。
例如输入 15,由于 1+2+3+4+5=4+5+6=7+8=15,所以结果打印出 3 个连续序列 1∼5、4∼6 和 7∼8。
数据范围
0≤S≤1000
样例
输入:15
输出:[[1,2,3,4,5],[4,5,6],[7,8]]
算法1
(双指针) $O(n)$
快慢双指针
C++ 代码
class Solution {
public:
int get_sum(int l, int r)
{
int cnt = r-l+1;
return cnt * (l+r)/2;
}
vector<int> add_ans(int l,int r)
{
vector<int> temp;
for(int i=l;i<=r;++i) temp.emplace_back(i);
return temp;
}
vector<vector<int> > findContinuousSequence(int sum)
{
vector<vector<int>> ans;
if(sum == 0 || sum ==1) return ans;
for(int i=1, j=1;j<sum;)
{
if(get_sum(i,j) < sum) j++;
else if(get_sum(i,j) > sum) i++;
else
{
ans.emplace_back(add_ans(i,j));
j++;
}
}
// int l=2,r=5;
// cout << get_sum(l,r)<<endl;
return ans;
}
};