剑指 Offer 57 - II. 和为s的连续正数序列-526互联

方法一：同向双指针

解题思路

使用两个双指针维护一个窗口，设窗口中元素的和为\(curSum\)。当\(curSum > target\)时，左指针右移一位；当\(curSum < target\)时，右指针右移一位；当\(curSum == target\)时，记录窗口内为一个答案，然后左右指针共同右移一位。
注意：由于\(窗口大小 >= 2\)，所以当\(r > target / 2 + 1\)时，窗口最小的值 \(r + (r - 1) > target\)，此时无意义，因此只取 \(r <= target / 2 + 1\)即可。

代码

class Solution {
public:
    vector<vector<int>> findContinuousSequence(int target) {
        vector<vector<int>> ans;
        int l = 1, r = 2, curSum = 3;
        // r 最多只能取target / 2 + 1，因为必须是两个连续数字，
        // 当r > target / 2 + 1时，r + r - 1 > target 没有意义，所以r取不到后面的值。
        while (r <= target / 2 + 1) { 
            while (curSum < target) {
                r ++ ;
                curSum += r;
            }
            while (curSum > target) {
                curSum -= l;
                l ++ ;
            }
            if (curSum == target) {
                vector<int> oneAns;
                for (int i = l; i <= r; i ++ ) oneAns.push_back(i);
                ans.push_back(oneAns);
                curSum -= l;
                l ++ ;
                r ++ ;
                curSum += r;
            }
        }
        return ans;
    }
};

复杂度分析

时间复杂度：\(O(target)\)；
空间复杂度：\(O(1)\)。