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