题目: 输入一个正整数 target ,输出所有和为 target 的连续正整数序列(至少含有两个数)。
序列内的数字由小到大排列,不同序列按照首个数字从小到大排列。
示例 1:
输入:target = 9
输出:[[2,3,4],[4,5]]
示例 2:
输入:target = 15
输出:[[1,2,3,4,5],[4,5,6],[7,8]]
思路:
https://www.bilibili.com/video/BV1RL4y1E7JC/?spm_id_from=333.788&vd_source=cc3333a27046bad449a2b6818cc4149c
思路:
如果right小于目标值时候,继续循环遍历,如果总和小于target,则right++,并讲该值加到sum中,
如果总和大于target了,说明以该left为起点的值找不到总和为target的,所以left++,
如果找到了总和后,循环遍历当前的left和right,加入到path中,说明当前以left开始的满足的条件,
下次就应该从left++开始了,因此从sum中减去left,再让left++,清除一下path,防止下次里边还有值。
class Solution {
public:vector<vector<int>> sumordered(int target) {vector<vector<int>> result;vector<int> path;int left = 1;int right = 2;int sum = left + right;while (right < target) {if (sum < target) {right++;sum += right;}else if (sum > target) {sum -= left;left++;}else {for (int i = left; i <= right; i++) {path.push_back(i);}sum -= left;left++;result.push_back(path);path.clear();}}return result;}
};int main() {int target = 9;Solution ss;vector<vector<int>> result = ss.sumordered(target);for (auto& res:result) {for (auto& ch:res) {cout << ch << " ";}cout << endl;}return 0;
}