用i
和j
分别表示序列的最大值和最小值,i
的初始值赋1
,j
的初始值赋2
,如果i
到j
的序列和大于sum
,可以从序列中去掉较小的值,也就是让i
后移;如果i
到j
的序列和小于sum
,则让j后移。
i
最多增加到(1+sum)/2
注意边界条件:sum < 3
时,结果都为空
class Solution {
public:
vector<vector<int> > findContinuousSequence(int sum) {
vector<vector<int>> res;
if (sum < 3) return res;
int i = 1, j = 2;
int mid = (1 + sum) / 2;
int cur_sum = i + j;
while (i < mid) {
if (cur_sum == sum) {
vector<int> line;
for (int k = i; k <= j; k++) line.push_back(k);
res.push_back(line);
}
while (cur_sum > sum && i < mid) {
cur_sum -= i;
i++;
if (cur_sum == sum) {
vector<int> line;
for (int k = i; k <= j; k++) line.push_back(k);
res.push_back(line);
}
}
j ++;
cur_sum += j;
}
}
};