剑指Offer57 - 数学/滑动窗口(双指针)

1. 题目描述

和为s的连续正数序列

2. 思路

O(N) 数学做法。

1. 等查求和公式，求根公式:\(\frac{-b \pm \sqrt{b*b - 4*a*c}}{2*a}\)
   求根公式在不少题目中的优化做法可能用到

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. 代码，双指针