剑指57-II：和为s的连续正数序列

传送门

nowcoder
leetcode

题目描述

找出所有和为 S 的连续正数序列，并输出该序列。
序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序。

C++ 代码 - nowcoder

/*
    滑动窗口
*/
class Solution {
public:
    vector<vector<int> > FindContinuousSequence(int sum) {
        vector<vector<int>> res;

        int low = 1, high = 2; // 滑动窗口：根据窗口内值的和，确定位置和大小
        while (low < high) {
            int curSum = (low + high) * (high - low + 1) / 2; // 差为 1 的等差数列
            if (curSum == sum) { // 和相等，将窗口范围的所有数添加进结果集
                vector<int> curRes;
                for (int i = low; i <= high; i ++) {
                    curRes.push_back(i);
                }
                res.push_back(curRes);
                low ++;
            } else if (curSum < sum) {
                high ++; // 和小于 sum，将右边窗口右移
            } else {
                low ++;  // 和大于 sum，将左边窗口右移
            }
        }

        return res;
    }
};

C++ 代码 - leetcode

/*
    双指针
    
    时间复杂度：O(target)
    空间复杂度：O(1)
*/
class Solution {
public:
    vector<vector<int>> fileCombination(int target) {
        vector<vector<int>> res;
        vector<int> curRes;

        int l = 1, r = 2; // 滑动窗口：根据窗口内值的和，确定窗口的位置和大小
        while (l < r) {
            int sum = (l + r) * (r - l + 1) / 2; // 窗口内的值之和，差为 1 的等差数列求和
            if (sum == target) {
                // 和相等，将窗口范围的所有数添加进结果集
                curRes.clear();
                for (int i = l; i <= r; i ++) {
                    curRes.emplace_back(i);
                }
                res.emplace_back(curRes);
                l ++;
            } else if (sum < target) {
                r ++; // 和小于 target，将右边窗口右移
            } else {
                l ++; // 和大于 target，将左边窗口右移
            }
        }

        return res;
    }
};