题意:
输出所有和为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; } };
时间复杂度:
空间复杂度:![]()