题意:
输出所有和为S的连续正数序列。
序列内按照从小至大的顺序,序列间按照开始数字从小到大的顺序。
例子如下:
方法一:
快慢指针
思路:快慢指针。
首先令l = r = 1,num = 0。如果num<给定值,则 num + = r , r++;
如果num>给定值,则 num - = l , l++;如果num == 给定值,则 得到一个解 [ l,r-1 ] ,后面再让 num - = l , l++,继续循环下去。
class Solution {
public:
vector<vector<int> > FindContinuousSequence(int sum) {
vector<vector<int>> res;//存储结果
vector<int> v;
int num=0,l=1,r=1;//快慢指针
while(l<=r&&r<sum){//循环
if(num<sum){
num+=r;//小于指定值,加右指针
r++;
}
if(num>sum){
num-=l;//大于指定值,减左指针
l++;
}
if(num==sum){//满足条件
for(int j=l;j<r;j++)
v.push_back(j);
res.push_back(v);
v.clear();
num-=l;
l++;
}
}
return res;
}
};
时间复杂度:
空间复杂度:![]()
方法二:
前缀和
思路:首先,计算前缀和数组;
再二重循环枚举左右区间取判断,并将满足条件的加入res。
class Solution {
public:
vector<vector<int> > FindContinuousSequence(int sum) {
vector<vector<int>> res;//存储结果
vector<int> v;
vector<int> x(sum,0);//前缀和
for(int i=1;i<sum;i++){
x[i]=x[i-1]+i;
}
for(int i=0;i<sum;i++){//枚举左右区间
for(int j=i+2;j<sum;j++){
if(x[j]-x[i]==sum){//满足条件
v.clear();
for(int k=i+1;k<=j;k++){
v.push_back(k);
}
res.push_back(v);
}
}
}
return res;
}
};
时间复杂度:
空间复杂度:![]()



京公网安备 11010502036488号