核心思想:acc
为累加和,快指针(j
)在前面扩展,慢指针(i
)在后面收缩。
时间复杂度:$O(2n)$,即$O(n)$。
class Solution {
public:
vector<vector<int> > findContinuousSequence(int sum) {
int i = 1, j = 0, acc = 0;
vector<vector<int>> all_ans;
while (j < sum / 2 + 1) {
// extend
do {
++j;
acc += j;
} while (acc < sum);
// shrink
while (acc > sum && i < j) {
acc -= i;
++i;
}
// check ans
if (acc == sum && j > i) {
vector<int> v;
for (int k = i; k <= j; ++k)
v.push_back(k);
all_ans.push_back(v);
}
} // j
return all_ans;
}
};