1. 题目描述
和为s的连续正数序列
2. 思路
O(N) 数学做法。
- 等查求和公式，求根公式: − b ± b ∗ b − 4 ∗ a ∗ c 2 ∗ a \frac{-b \pm \sqrt{b*b - 4*a*c}}{2*a} 2∗a−b±b∗b−4∗a∗c
求根公式在不少题目中的优化做法可能用到，但是需要注意，求根公式有乘法运算，对于数据比较大时，可能会溢出，这一点要格外小心。
O(N) 双指针
1
3. 代码，数学做法
class Solution {
public:vector<vector<int>> findContinuousSequence(int target) {vector<vector<int>> res;for(int i = 1; i < target; i ++ ) {long long k = (long long)target * 2 + (long long)i * i - i;int s = (sqrt(1 + 4 * k) - 1) / 2;if((long long)s * s + s - k == 0) {vector<int> path;for(int j = i; j <= s; j ++ ) path.push_back(j);res.push_back(path);}}return res;}
};/* 等差数列和公式
[a,...,b]
s = (b + a) / 2 * (b - a + 1)
s = (b + a) * (b - a + 1) / 2
b^2 - a^2 + a + b = s * 2
b^2 + b = s*2 +a^2 - a
*/
4. 代码，双指针
class Solution {
public:vector<vector<int>> findContinuousSequence(int target) {int sum = 0;vector<vector<int>> res;for(int i = 1, j = 1; i < target; i ++ ) {while(sum < target) {sum += j;j ++ ;}if(sum == target) {vector<int> path;for(int k = i; k < j; k ++ ) path.emplace_back(k);res.emplace_back(path);}sum -= i;}return res; }
};
