关于leetcode:每日一练30和为s的连续正数序列

title: 每日一练（30）：和为 s 的间断负数序列

categories:[剑指 offer]

tags:[每日一练]

date: 2022/03/04

每日一练（30）：和为 s 的间断负数序列

输出一个正整数 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

起源：力扣（LeetCode）

链接：https://leetcode-cn.com/probl…

办法一：暴力求和公式

vector<vector<int>> findContinuousSequence(int target) {if (target < 3) {return {};
    }
    int left = 1;
    double right = 2.0;
    vector<vector<int>> res;
    while (left < right) {right = (-1 + sqrt(1 + 4 * (2 * target + (long)left * left - left))) / 2;
        if (left < right && right == (int) right) {
            vector<int> ans;
            for (int i = left; i <= (int)right; i++) {ans.push_back(i);
            }
            res.push_back(ans);
        }
        left++;
    }
    return res;
}

办法二：滑动窗口

算法流程：
1. 初始化：左边界 left =，右边界 right = 2，元素和 sum = 3，后果列表 res；

2. 循环：当 left >= right 时跳出；

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

3. 返回值：返回后果列表 res；

vector<vector<int>> findContinuousSequence(int target) {if (target < 3) {return {};
    }
    int left = 1, right = 2, sum = 3;
    vector<vector<int>> res;
    while (left < right) {if (sum == target) {
            vector<int> vec;
            for (int i = left; i <= right; i++) {vec.push_back(i);
            }
            res.push_back(vec);
        }
        if (sum >= target) {
            sum -= left;
            left++;
        } else {
            right++;
            sum += right;
        }
    }
    return res;
}