休了个不短不长的年假，题解系列持续动工~
本专题旨在分享刷 Leecode 过程发现的一些思路乏味或者有价值的题目。
题目相干
- 原题地址: https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/]
-
题目形容：
输出一个正整数 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
思路解析
- 示例 1：
暴力破解
题目的含意比拟清晰，需要求出和为特定值的 间断正整数序列。
首先，这道题的很间接的也会想到一个 — 暴力破解:
具体思路：
- 首先寻找是否存在满足要求的，以 1 为结尾的序列，所以初始化一个序列为
[1] -
顺次往序列里增加间断的正整数，让序列变成
[1, 2, 3..i. target]，并且每次增加完一个整数时，比照以后序列所有整数之和 sum，与目标值 target 的关系：- 如果
sum < target，则持续往序列里增加下一个数； - 如果曾经满足
sum = target，那么 存储以后序列 ，并且阐明 以 1 开始的序列寻找能够进行了； - 如果间接到
sum > target，那么阐明 以 1 开始的序列寻找能够进行了（不存在以 1 为结尾并且满足要求的序列）；
- 如果
- 反复上述步骤，别离寻找以 2，3, … target 结尾且满足题意的序列；
下面这种思路的话 最坏的状况下，须要外层循环（外层循环也就是遍历以 1..n 结尾的序列）n次，内层循环 n 次（内层循环就是寻找以后结尾固定时，不同结尾的序列），那么总的复杂度就是 O(n^2)，因为 1 <= target <= 10^5 , 所以O(n^2) 显著超时;
红色区域示意序列，它的左边界和右边界有个特点，都 只向右侧挪动，而整个遍历的过程，其实就像是一个推拉窗的挪动过程，这个算法也就由此得名。
滑动窗口
从上述过程能够看到，暴力破解的问题在于 工夫复杂度太高 ，而之所以高，是因为 在遍历过程存在一些能够跳过的过程 , 为了便于了解，咱们带入一个题设中的示例 1，target = 9 的状况来进行演示。依照暴力破解思路：
- 首先序列为
[1], 序列之和sum = 1, 1 < 9 持续循环; - 序列为
[1, 2], 序列之和sum = 3, 3 < 9 持续循环; - 序列为
[1, 2，3], 序列之和sum = 6, 6 < 9 持续循环; - 序列为
[1, 2, 3 ,4], 序列之和sum = 12, 12 > 9 , 那 Stop!;
到此阐明不存在 以 1 为结尾切满足要求的序列，那么依照后面的思路，接下来是要寻找以 2 结尾且满足题意的序列，那么当初问题来了：
咱们真的有必要从 [2] 开始吗？在找以 1 结尾的序列时，咱们曾经发现 [1,2,3] 之和都小于 target 了，那序列 [2,3] 之和必定也小于 9，那为什么还要循序渐进的，先走一次 [2] 再到 [2,3] 再到[2,3,4] 呢？
这，就是冲破的要害！
所以咱们发现，再找完以 i 结尾的序列之后，跳到寻找以 i + 1 结尾的序列时，是能够跳过一些两头遍历次数的，能够这么做:
- 序列为
[1, 2, 3 ,4], 序列之和sum = 12，12 < 9，此时要进行寻找以 1 为结尾的序列 ，那么咱们间接去掉序列右边的值，从[2,3,4]开始寻找以 2 结尾的序列； - 依照规定，
[2, 3 ,4]之和刚好为9，此时保留以后序列后果，并且 进行寻找以 2 为结尾切满足要求的序列 ，接下来筹备寻找 3 结尾的序列，咱们 同样去掉此时序列的最右边值, 从[3, 4]开始运算；
反复上述过程，会发现，在遍历过程中，咱们的序列如下图所示（懒得做动图了，离开看更有利于了解）:
红色区域示意序列，它的 左边界 和右边界 有个特点，都 只向右侧挪动 ，而整个遍历的过程，其实就像是一个 推拉窗 的挪动过程，这个算法也就由此得名。
当然，要应用下面的算法，咱们要答复一个问题：相较于暴力破解，滑动窗口的确缩小了循环次数，然而滑动窗口是否找到所有的解呢？（也就是在上述的跳跃过程导致脱漏呢？）
这个是能够证实的，因为依照前文的遍历思路：
- 寻找 1 结尾的序列时，只有序列之和小于
target，则 窗口右边界始终往右拓展 ，直到找到[1,2,3]时，此时序列值之和还是小于target; 而到[1,2,3,4]时，此时序列之和第一次大于target，阐明 以 1 结尾的序列寻找完结; - 那么此时以 2 结尾的序列
[2,3]<[1,2,3]<target，阐明 只须要从 [2,3,4] 开始寻找 就能够了，（读者敌人也能够拿示例 2 带入试试看，加深了解）以此类推，阐明滑动窗口的算法是不会有脱漏的。
残缺代码
到这里只须要整顿后面的思路，伪代码也就进去了：
- 初始化，设定序列窗口的左右边界，别离为
1,2，而后开始循环； - 循环，当序列内之和小于 target 时，右边界右移；
- 循环过程如果发现 序列值和等于 target，则存储以后序列，并且把左边界右移；
- 循环过程如果发现 序列值和大于 target，则把左边界右移；
- 当左边界追上右边界时，循环完结（能够思考下为什么？）
那么理论代码如下：
var findContinuousSequence = function(target) {const res = [];
const sum = [0, 1];
let l = 1; // 左边界
let r = 2; // 右边界
let s = 3; // 以后序列之和 sum
while(l < r){if(s === target) {
// 满足题意的序列增加到后果
res.push(getList(l, r));
}
if(s > target) {
s = s - l;
l++;
} else {
r++;
s += r;
}
}
return res;
};
function getList (l, r) {const res = [];
for(let i = l; i<=r; i++) {res.push(i)
}
return res;
}那么滑动窗口的内容就到此为止了~
此外 …
在文章开端顺便打个小广告，问下有没有想来外企 955 的小伙伴：
- 面朝大海办公，不打卡 不考勤 到点就上班，工作生存两不误；
- 假期超长（每年年假 + 带薪病假 + 企业年假 = 20 天起步！）；
- 而且很多岗位能够 长期近程办公！不再困扰与一线昂扬房价难落地的问题；
- 可内推，base 杭州和厦门~