LeetCode 剑指 Offer 57 - II. 和为s的连续正数序列
原题链接
简单
作者:
RiseAbove1
,
2023-01-09 21:33:38
,
所有人可见
,
阅读 133
剑指 Offer 57 - II. 和为s的连续正数序列
class Solution {
public:
vector<vector<int>> findContinuousSequence(int target) {
//这题使用滑动窗口,思路很简单,但是要想写出来,还是有一定难度的
int i = 1 , j = 1;//滑动窗口的左右边
int sum = 0;//滑动窗口的总和
vector<vector<int>>ans;
while(i<=target/2){//输出所有和为 target 的连续正整数序列(至少含有两个数),因为要两个数,所以截止条件就是当i>target/2时截止
if(sum<target){//小了,右边界右移
sum += j;//if在判断的时候,并没有加上j,左闭右开
j++;//右移
}else if(sum>target){//大了,左边界右移
sum -= i;
i++;//还是右移
}else{
vector<int>tmp;//临时变量
for(int k = i ; k < j ; k++)//左闭右开
tmp.push_back(k);
ans.push_back(tmp);
//左边界继续右移
sum -= i;
i++;
}
}
return ans;
}
};