剑指offer刷题系列：
面试题57 - II. 和为s的连续正数序列
暴力解法：
针对每种解法检查是否可以等于target
/**
* @param {number} target
* @return {number[][]}
*/
var findContinuousSequence = function(target) {
if(target<3) {
return [];
}
let max = Math.ceil(target/2);
let res = [];
for(let i = 1; i < max; i++) {
for(let j = i+ 1; j <= max; j++) {
let sum = (i+j)*(j-i+1)/2;
if(sum === target) {
res.push(get(i, j));
}
}
}
return res;
};
function get(i, j) {
let res = [i];
let val = i;
while(val < j) {
res.push(val+1);
val++;
}
return res;
}
结果超出了时间限制
改用双指针，滑动窗口
/**
* @param {number} target
* @return {number[][]}
*/
var findContinuousSequence = function(target) {
if(target<3) {
return [];
}
let p = 1;
let q = 2;
let max = Math.ceil(target/2);
let res = [];
while(p < max && q <= max) {
let sum = (p+q)*(q-p+1)/2;
if(sum === target) {
res.push(get(p, q));
p++;
} else if(sum < target) {
q++;
} else {
p++;
}
}
return res;
};
function get(i, j) {
let res = [i];
let val = i;
while(val < j) {
res.push(val+1);
val++;
}
return res;
}
关于滑动窗口，这里有篇文章讲的挺清晰的，可以参考一下：
https://zhuanlan.zhihu.com/p/107786714?utm_source=wechat_session&utm_medium=social&utm_oi=1047235829767958528
