题目
输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。 序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。 难易程度：easy
示例 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
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题解
分析
本题方法比较多，如暴力遍历，双指针法等，这里只介绍利用数学公式来求解的方法。
本题本质上是序列求和问题，此类问题的一个经典问题就是求1,...,100这100个数之和。当年高斯使用的方法就是(1 100)*100/2。
设s < x 且s,...,x这(x - s 1)个连续整数之和为target。那么，有(s x)*(x -s 1) == 2 * target,即存在一元二次方程:
x^2 x s*(1-s) - 2*target = 0。
根据韦达定理解得：
x = (sqrt(1-4(s*(1-s) - 2*target)) - 1) / 2
最终本题转变成有多少个[s, x]区间的问题，即枚举s的情况下求解一元二次方程:x^2 x s*(1-s) - 2*target = 0 整数正值的问题。
时间复杂度：O(N)，由于枚举以后只需要 O(1)的时间判断，所以时间复杂度为枚举起点的复杂度O(target/2) 。 空间复杂度：O(1) ，除了答案数组只需要常数的空间存放若干变量。
代码
代码语言：javascript复制class Solution {
public:
vector<vector<int>> findContinuousSequence(int target) {
vector<vector<int>> res;
// 题中要求至少含有两个数，所以s最大为target-1
for (int s = 1; s <= target / 2; s ) {
// 主要这里s*(1-s)可能超过MAX_INT，因此同乘以1ll来提升类型，下同
long long d = 1 - 4*(1ll * s*(1 - s) - 2 * target);
if (d < 0) {
continue;
}
int sqrt_d = (int)sqrt(d);
if (1ll * sqrt_d * sqrt_d == d && (sqrt_d - 1) % 2 == 0) {
vector<int> tmp;
for (int i = s; i <= (sqrt_d - 1) / 2; i ) {
tmp.push_back(i);
}
res.push_back(tmp);
}
}
return res;
}
};
