Ex57-II 和为s的连续正数序列

题目描述

输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。 序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。

解题思路

从1到target/2+1开始遍历，记录start，开始相加，当sum为target时，将从start到现在的数字放到返回结果中；当sum大于target时，将start前移，并停止遍历。

代码

class Solution {
 public:
  std::vector<std::vector<int>> findContinuousSequence(int target) {
    std::vector<std::vector<int>> res;
    if (target == 1) {
      res.push_back(std::vector<int>{1});
      return res;
    }
    int sum = 1;
    int start = 1;
    for (int i = 2; i <= target / 2 + 1; ++i) {
      if (sum + i == target) {
        res.push_back(vector_from_start_to_end(start, i));
        sum += i - start;
        ++start;
      } else if (sum + i < target) {
        sum += i;
        continue;
      } else {  // sum + i > target
        sum -= start;
        --i;
        ++start;
      }
    }
    return res;
  }

 private:
  std::vector<int> vector_from_start_to_end(int start, int end) {
    std::vector<int> vec;
    for (int i = start; i <= end; ++i) {
      vec.push_back(i);
    }
    return vec;
  }
};

结果

执行结果：通过

执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户

内存消耗：6.8 MB, 在所有 C++ 提交中击败了65.37%的用户