AcWing 76. 和为S的连续正数序列
原题链接
中等
作者:
明天堂
,
2024-01-13 23:08:54
,
所有人可见
,
阅读 39
双指针法
一般思路:
双指针的思路模板一般为,一个快针,一个慢针,慢针做起点,快针遍历,当满足一定条件时,输出,同时更新起点,快针继续遍历
本题思路复述:
i
作为慢针在前面固定起点,j
作为快针,往后遍历数组,计算累加和
- 若累加和等于sum,则记录该子序列
- 更新起点,将i从累加和中移除,如果这里不懂的话可以手动模拟一下
1 5 15
2 6 20
3 6 18
4 6 15
5 7 18
6 8 21
7 8 15
class Solution {
public:
vector<vector<int> > findContinuousSequence(int sum) {
vector<vector<int>> res; // 用来存放答案
for(int i = 1,j = 1,s = 1;i <= sum / 2;i++)
{
while(s < sum) s += ++j;
if(s == sum && j - i + 1 > 1)
{
vector<int> a;
for(int k = i;k <= j;k++) a.push_back(k);
res.push_back(a);
}
s -= i; // 把这个起点移除和,已达到更新起点的作用
}
return res;
}
};