输入一个正整数 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。