剑指 Offer 57 - II. 和为s的连续正数序列
思路:滑动窗口
- 初始化:左边界i=1,有边界j=2,元素和s=3,结果列表res
- 循环:当i>=j跳出:
- 当s>target:向右移动左边界i=i+1,并更新元素和
- 当s<target:向右移动有边界j=j+1,并更新元素和
- 当s==target:记录整数序列,并向右移动左边界i=i+1
- 返回值:res
class Solution {
public:
vector<vector<int>> findContinuousSequence(int target) {
int i=1,j=2,sum=i+j;
vector<vector<int>> ans;
while(i<j){
if(sum<target){
j=j+1;
sum+=j;
}
else if(sum>target){
sum-=i;
i++;
}
else{
vector<int> res(j-i+1);
for(int k=0;k<j-i+1;++k){
res[k]=k+i;
}
ans.push_back(res);
sum-=i;
++i;
}
}
return ans;
}
};
时间复杂度 O(n) n是target
空间复杂度 O(1)