暴力
枚举区间起点 i
,对于每一个 i
,找到最大的 j
,满足 ij 区间和<target
class Solution {
public:
vector<vector<int> > findContinuousSequence(int sum) {
vector<vector<int> > res;
for (int i = 1; i < sum; i ++ )
{
int j=i,t=0;
vector<int> q;
while(t<sum)
{
t+=j;
q.push_back(j);
j++;
}
if(t==sum) res.push_back(q);
}
return res;
}
};
二分优化
寻找 j
的过程可以使用二分,复杂度降为O(nlogn)
双指针优化
可以发现,i
后移,j
单调后移,可以使用双指针优化掉一层循环,复杂度降为O(n)
class Solution {
public:
vector<vector<int> > findContinuousSequence(int sum) {
vector<vector<int> > res;
for (int i = 1,j=1,s=0; i < sum; i ++ )
{
while(s<sum)
{
s+=j;
j++;
}
if(s==sum)
{
vector<int> q;
for (int k = i; k < j; k ++ ) q.push_back(k);
res.push_back(q);
}
s-=i;
}
return res;
}
};
标签:int,res,sum,++,vector,连续,序列,正数,复杂度
From: https://www.cnblogs.com/tangxibomb/p/17388012.html