题目描述
输入一个正数s,打印出所有和为s的连续正数序列(至少含有两个数)。
例如输入15,由于1+2+3+4+5=4+5+6=7+8=15,所以结果打印出3个连续序列1~5、4~6和7~8。
样例
输入:15
输出:[[1,2,3,4,5],[4,5,6],[7,8]]
算法1
利用deque数据结构 $O(n)$
利用deque存储当前的序列,并用一个变量记录当前的和,如果和太大,弹出队首,和太小尾部加上一个数,如果和正好是想要的数,把deque中的序列加到结果中即可。
时间复杂度
参考文献
C++ 代码
// deque method, time O(n), space O(n)
class Solution {
public:
vector<vector<int> > findContinuousSequence(int sum) {
if (sum <= 0) return{};
deque<int> dq; dq.push_back(1);
vector<vector<int>> res;
int s = 1;
while (dq.back() <= sum / 2 + 1) {
if (s < sum) dq.push_back(dq.back() + 1), s += dq.back();
else if (s > sum) s -= dq.front(), dq.pop_front();
else res.push_back(vector<int>(dq.begin(), dq.end())), dq.push_back(dq.back() + 1), s += dq.back();
}
return res;
}
};
算法2
双指针 $O(n)$
算是基于上述deque方法的一种优化,计算过程中,只需要记录序列首尾以及当前的和即可,不需要把序列中的数都存着。
时间复杂度
两个指针最多指到约sum / 2, 故时间复杂度位O(n)
参考文献
C++ 代码
// 2 pointers method, time O(n), space O(1)
class Solution {
public:
vector<vector<int> > findContinuousSequence(int sum) {
if (sum <= 0) return{};
int i = 1, j = 1, s = 1;
vector<vector<int>> res;
while (j <= sum / 2 + 1) {
if (s < sum) s += ++j;
else if (s > sum) s -= i++;
else {
vector<int> path;
for (int num = i; num <= j; ++num) path.push_back(num);
res.push_back(path);
s += ++j;
};
}
return res;
}
};