// 滑动窗口算法解题思路
1. 使用双指针技巧，初始化left=right=0,把索引左闭右开区间[left, right）称为一个窗口
2. 先不断增加right指针，扩大窗口
3. 当结果不符合要求，进行窗口收缩
4. 重复2、3步，直到终止条件和为s的连续正数序列
输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。
示例 1：
输入：target = 9 输出：[[2,3,4],[4,5]]
// 该问题是一个滑动窗口问题
// 滑动窗口算法解题思路
// 1. 使用双指针技巧，初始化left=right=0,把索引左闭右开区间[left, right）称为一个窗口
// 2. 先不断增加right指针，扩大窗口
// 3. 当结果不符合要求，进行窗口收缩
// 4. 重复2、3步，直到终止条件
function findContinuousSequence(target) {
const result = [];
// 滑动窗口
const window = [];
let sum = 0;
const middle = (target + 1) << 1;
let left = 1;
let right = 1;
for (let i = 1; i <= middle; i++) {
// 扩充窗口
window.push(i);
sum += i;
right++;
// 判断是否收缩窗口
while (sum > target) {
// 进行窗口收缩
const temp = window.shift();
left++;
sum -= temp;
}
if (sum === target && window.length > 1) {
result.push([...window]);
}
}
return result;
}
console.log(findContinuousSequence(9));最长不含重复字符的子字符串
请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
示例 1:
输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
// 可以通过滑动窗口解决
function lengthOfLongestSubstring(s) {
// 滑动窗口
const window = {};
// 左右指针
let left = 0;
let right = 0;
let result = 0;
for (let i = 0; i < s.length; i++) {
const c = s.charAt(i);
// 扩充窗口
window[c] = window[c] ? window[c] + 1 : 1;
right++;
// 判断是否收缩窗口
while (window[c] > 1) {
// 进行窗口收缩
const leftC = s.charAt(left);
window[leftC]--;
left++;
}
result = Math.max(result, right - left);
}
return result;
}
const s = 'abcabcbb';
console.log(lengthOfLongestSubstring(s));长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
示例 1：
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。// 滑动窗口
function minSubArrayLen(target, nums) {
let left = 0;
let right = 0;
let sum = 0;
let result = Infinity;
while (right < nums.length) {
// 更新状态
sum += nums[right];
right++;
// 收缩窗口
while (sum >= target) {
result = Math.min(result, right - left);
const presentVal = nums[left];
// 更新状态
sum -= presentVal;
left++;
}
}
return result === Infinity ? 0 : result;
}无重复字符的最长子串
一、题目
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
二、题解
function lengthOfLongestSubstring(s) {
// 滑动窗口
const window = {};
// 滑动窗口的两个指针
let left = 0;
let right = 0;
// 结果
let result = 0;
// 循环终止条件
while (right < s.length) {
const c = s[right];
// 进行窗口内数据的一系列更新
window[c] = window[c] ? window[c] + 1 : 1;
// 移动窗口右侧
right++;
// 判断左侧窗口是否要收缩
while (window[c] > 1) {
const d = s[left];
// 左侧窗口收缩
left++;
// 进行窗口内的一系列更新
window[d]--;
}
// 更新答案
result = Math.max(result, right - left);
}
return result;
}
const s = 'abcabcbb';
console.log(lengthOfLongestSubstring(s));字符串排列
一、题目
给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。
换句话说，s1 的排列之一是 s2 的 子串 。
示例 1：
输入：s1 = "ab" s2 = "eidbaooo" 输出：true 解释：s2 包含 s1 的排列之一 ("ba").
二、题解
function checkInclusion(s1, s2) {
// 需要凑齐的字符
const need = {};
for (let i = 0; i < s1.length; i++) {
need[s1[i]] = need[s1[i]] ? need[s1[i]] + 1 : 1;
}
// 滑动窗口
const window = {};
// 滑动窗口的两端
let left = 0;
let right = 0;
// 表示窗口中满足need部分的字符数
let valid = 0;
while (right < s2.length) {
const c = s2[right];
// 进行窗口内数据的一系列更新
if (need[c]) {
window[c] = window[c] ? window[c] + 1 : 1;
if (window[c] === need[c]) {
valid++;
}
}
// 移动窗口右侧
right++;
// 判断左侧窗口是否要收缩（当s1字符和滑动窗口字符大小相等，此时就要收缩敞口）
while (right - left >= s1.length) {
// 在这里判断是否找到了合法的子串
if (valid === Object.keys(need).length) {
return true;
}
const d = s2[left];
left++;
// 进行窗口内数据的一系列更新
if (need[d] !== undefined) {
if (window[d] === need[d]) {
valid--;
}
window[d]--;
}
}
}
return false;
}
const s1 = 'ab';
const s2 = 'eidbaooo';
console.log(checkInclusion(s1, s2));滑动窗口的最大值
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
示例 1：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3 输出：[3,3,5,5,6,7] 解释： 滑动窗口的位置最大值
[1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7
该问题用单调队列解决（单调队列可以解决滑动窗口问题）。
// 首先建立一个单调队列的类
class MonotonicQueue {
constructor() {
this.queue = [];
}
// 在队尾添加元素n
// 该函数在加入元素时，会将其前面比自己小的元素全部删除掉
push(n) {
// 将前面小于自己的元素全部删除掉
while (this.queue.length && n > this.queue[this.queue.length - 1]) {
this.queue.pop();
}
this.queue.push(n);
}
// 对头元素如果是n，则删除它
pop(n) {
if (this.queue.length > 0 && n === this.queue[0]) {
this.queue.shift();
}
}
// 返回当前队列中的最大值
// 因为push元素时都会将比自己小的删除掉，最终结果就是一个递减的顺序，则最大值就是队列首部内容
max() {
return this.queue[0];
}
}
function maxSlidingWindow(nums, k) {
// 实例化一个单调队列
const monotonicQueue = new MonotonicQueue();
const result = [];
for (let i = 0; i < nums.length; i++) {
// 先填满整个滑动窗口的k-1个元素
if (i < k - 1) {
monotonicQueue.push(nums[i]);
} else {
// 窗口向前滑动，添加新元素
monotonicQueue.push(nums[i]);
// 记录当前窗口的最大值
result.push(monotonicQueue.max());
// 移除队列首部元素
monotonicQueue.pop(nums[i - k + 1]);
}
}
return result;
}
