输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。

序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。 示例 1：

输入：target = 9 输出：[[2,3,4],[4,5]] 示例 2：

输入：target = 15 输出：[[1,2,3,4,5],[4,5,6],[7,8]]

限制：

1 <= target <= 10^5

暴力解，通过

注意，子序列长度大于等于二，所以我们循环以二分之一个目标作为结束标志，当然也要注意一下要不要+1，以及循环结束条件是小于等于还是等于的问题。 AC代码：

class Solution { public: vector<vector<int>> findContinuousSequence(int target) { int start = 1; vector<vector<int>>result; vector<int>smallresult; int half_target = (target*0.5) + 1; while (start <= half_target) { int sum = 0; int flag = 0; smallresult.clear(); for (int i = start;i <= half_target;i++) { flag = 1; sum += i; smallresult.push_back(i); if (sum > target) { break; } else if (sum == target) { result.push_back(smallresult); break; } } if (flag == 1) start++; } return result; } };

优化暴力解

优化之后的代码：仍然是暴力法，不过将push_back换成了emplace_back，然后将插入和清除操作放入了sum == target的逻辑块中，减少了插入以及删除元素带来的时间损失。

class Solution { public: vector<vector<int>> findContinuousSequence(int target) { int start = 1; vector<vector<int>>result; vector<int>smallresult; int half_target = (target*0.5) + 1; while (start <= half_target) { int sum = 0; int flag = 0; for (int i = start;i <= half_target;i++) { flag = 1; sum += i; if (sum > target) { break; } else if (sum == target) { smallresult.clear(); for(int j=start;j<=i;j++) smallresult.emplace_back(j); result.emplace_back(smallresult); break; } } if (flag == 1) start++; } return result; } };

再次优化思路

一开始我列下了两个优化思路： 1、若只有一组结果，或者没有结果，能不能找到一种方法直接返回结果 2、如果已经完成一组结果，下一组的推断能不能用到上一组的信息。 接下来就是一大堆乱改步长的操作，也就是说，之前每完成一次子序列和没有完成子序列，下一次的起始点都是原起始点+1，此时我们不这样做，而是在完成一次子序列后，修改下一次的起始点。 修改思路： 此处的i是指完成一次子序列时的子序列的右边界 1、new_start=(i+start)0.5+1; （经过验证，是错误的） 2、new_start= i0.5+1； (经过验证，是错误的） 3、new_start=start+2; 这个倒是可以。。。不过优化不是很多

双指针（滑动窗口）

我们用两个指针 L 和 R 表示当前枚举到的以 L 为起点到 R 的区间，sum 表示[L,R]的区间和，由求和公式可知; 也就是说，如果确定了一对L、R，就可以直接得到sum值，而不需要累加计算了（省时序） 如果sum<target 则说明指针R还可以向右拓展使得sum 增大，此时指针R向右移动，即 r+=1 如果sum>target 则说明以L为起点不存在一个R使得 sum=target，此时要枚举下一个起点，指针L向右移动，即l+=1 如果sum==target 则说明我们找到了以L为起点得合法解 [l,r]，我们需要将 [l,r][l,r] 的序列放进答案数组，且我们知道以L为起点的合法解最多只有一个，所以需要枚举下一个起点，指针L向右移动，即 l+=1 (题外话，官方解的第三种方法讲解有问题。。。) 而且感觉这个方法也没有用到区间信息，只是高级在使用了公式。

class Solution { public: vector<vector<int>> findContinuousSequence(int target) { vector<vector<int>>vec; vector<int> res; for (int l = 1, r = 2; l < r;){ int sum = (l + r) * (r - l + 1) / 2; if (sum == target){ res.clear(); for (int i = l; i <= r; ++i) res.emplace_back(i); vec.emplace_back(res); l++; } else if (sum < target) r++; else l++; } return vec; } };

另外还发现了一个C++语法的问题： c++11 之emplace_back 与 push_back的区别 总结就是能用emplace_back就用emplace_back。