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

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

难度：$easy$

题目描述

输入一个正整数 $target$ ，输出所有和为 $target$ 的连续正整数序列（至少含有两个数）。

序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。

示例 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$

算法

(双指针)

设连续正整数序列的左边界 left 和右边界 right ，则可构建滑动窗口从左向右滑动。循环中，每轮判断滑动窗口内元素和与目标值 target 的大小关系，若相等则记录结果，若大于 target 则移动左边界 left （以减小窗口内的元素和），若小于 target 则移动右边界 right （以增大窗口内的元素和）。

算法流程：

1. 初始化： 左边界 left = 1 ，右边界 right = 2 ，元素和 sum = 3 ，结果列表 ans ，中间数 middle = (target + 1) / 2；

2. 循环： 当 left ≥ middle 时跳出；

   • 当 sum>target 时： 向右移动左边界 left = left + 1 ，并更新元素和 sum ；
   • 当 sum<target 时： 向右移动右边界 right = right+1 ，并更新元素和 sum ；
   • 当 sum=target 时： 记录连续整数序列，并向右移动左边界 left = left+1 ；

3. 返回值： 返回结果列表 ans ；

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是数组的长度。需要遍历数组一次。

• 空间复杂度 : $O(1)$

C++ 代码

class Solution {
public:
    vector<vector<int>> findContinuousSequence(int target) {
        vector<vector<int>> ans;

        int left = 1, right = 2;
        int middle = (target + 1) / 2;
        int sum = left + right;

        vector<int> res;
        while (left < middle) {
            if (sum == target) {
                for (int i = left; i <= right; i ++)
                    res.push_back(i);
                ans.push_back(res);
                res.clear();
            }
            
            while (sum > target && left < middle) {
                sum -= left;
                left ++;

                if (sum == target) {
                    for (int i = left; i <= right; i ++)
                        res.push_back(i);
                    ans.push_back(res);
                    res.clear();
                }
            }

            // sum < target;
            right ++;
            sum += right;
        }

        return ans;
    }
};