题目
输入一个正数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. 设置两个指针i和j,分别指向连续正数序列的起始和终止
  2. 用s表示当前连续正数序列的和,即s=i+(i+1)+…+js=i+(i+1)+…+j
  3. 以i递增的方式遍历整个序列(1到n),代表查找以i开头的时候结尾j应该是多少。当ssum说明向后走即可。
  4. 注意上述遍历过程中,s=sum的情况下不需要把j往前移动,原因是当进入下一个循环前s−=i,即(i+1)到j的和肯定小于sum。

时间复杂度O(n),空间复杂度O(n2)

  1. class Solution {
  2. public:
  3. vector<vector<int> > findContinuousSequence(int sum) {
  4. vector<vector<int>> ans;
  5. for (int i = 1, j = 1, s = 1; i < sum; i++) {
  6. while (s < sum) j++, s += j;
  7. if (sum == s && i < j) {
  8. vector<int> t;
  9. for (int k = i; k <= j; k++)
  10. t.push_back(k);
  11. ans.push_back(t);
  12. }
  13. s -= i;
  14. }
  15. return ans;
  16. }
  17. };