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;}