剑指 Offer 57 - II. 和为s的连续正数序列
题目内容
输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。
示例 1：
1
2
| 输入：target = 9
输出：[[2,3,4],[4,5]]
|
示例 2：
1
2
| 输入：target = 15
输出：[[1,2,3,4,5],[4,5,6],[7,8]]
|
限制：
解法一:滑动窗口
思路：
窗口何时扩大，何时缩小？
- 当窗口的和小于 target 的时候，窗口的和需要增加，所以要扩大窗口，窗口的右边界向右移动
- 当窗口的和大于 target 的时候，窗口的和需要减少，所以要缩小窗口，窗口的左边界向右移动
- 当窗口的和恰好等于 target 的时候，我们需要记录此时的结果。设此时的窗口为 [i, j)，那么我们已经找到了一个 i 开头的序列，也是唯一一个 i 开头的序列，接下来需要找 i+1 开头的序列所以窗口的左边界要向右移动
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public:
vector<vector<int>> findContinuousSequence(int target) {
vector<vector<int>> res;
int l = 1,r = 1,sum = 0;
while(l <= target / 2){
if(sum < target){
sum += r++;
}else if(sum> target){
sum -= l++;
}else{
vector<int> temp;
for (int i = l; i < r ; i++) temp.push_back(i);
res.push_back(temp);
sum -= l++;
}
}
return res;
}
};
|
结果：
1
2
3
4
5
6
7
8
9
10
| 执行用时：
0 ms
, 在所有 C++ 提交中击败了
100.00%
的用户
内存消耗：
6.5 MB
, 在所有 C++ 提交中击败了
61.57%
的用户
|
