十五周算法訓練營——滑動窗口
作者：前端點線面
今天是十五周算法訓練營的第七周，主要講滑動窗口專題。
// 滑動窗口算法解題思路
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").
二、題解
/**
* 算法思路：
* 滑動窗口
* s2包含s1的最小子串，然后最小子串長度跟s1長度相等
*/
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;
}責任編輯：姜華
來源：
前端點線面
