【算法】滑动窗口

参考链接

无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

示例

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
1
2
3
4
5
6
7
8

解法： 滑动窗口str中是没有重复的连续子串，当遍历字符串s时，当发现s[i]在滑动窗口str中出现了，则 将窗口右移一位并添加上当前字符s[i]

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    // if(s.length === 1){
    //     return 1;
    // }
    let subStr = '';
    let maxV = 0;
    for(let i=0;i<s.length;i++){
        let idx = subStr.indexOf(s[i]);
        if(idx===-1){
            subStr += s[i];
        }else{
            subStr = subStr.slice(idx+1)+s[i];
        }
        if(maxV<subStr.length){
                maxV = subStr.length;
        }
    }
    return maxV;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

串联所有单词的子串

最小覆盖子串

题目： 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。
示例：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。
1
2
3
4
5
6

题解： 利用滑动窗口在s中从头开始滑动，当窗口中的字符包含所有t中字符时，考虑缩小窗口，否则增大窗口
这里利用一个map数据结构来判断当前窗口是否包含所有t中字符，如果向右增大窗口时，当前字符s[right]在map中，则map对应位置减1，代表该字符在窗口出现了。而缩小窗口时，如果s[left]在map中，将map对应位置加1，表示该字符从窗口中移除了。
leetcode链接

/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
var minWindow = function(s, t) {
    // 记录当前窗口是否已经包含t中所有字符
    let map = new Map();
    for(let i=0;i<t.length;i++){
        if(map.has(t[i])){
            let tmp = map.get(t[i])
            map.set(t[i], tmp+1);
        }else{
            map.set(t[i], 1);
        }
    }
    let left=0, right=0;
    let startIdx = 0, maxLen = Number.MAX_SAFE_INTEGER;
    while(right<s.length){
        if(map.has(s[right])){
            map.set(s[right], map.get(s[right])-1);
        }
        right++;
        while(check(map)){//当前窗口包含了t,考虑缩小窗口
            if(maxLen>right-left){
                maxLen = right - left;
                startIdx = left;
            }
            if(map.has(s[left])){
                map.set(s[left], map.get(s[left])+1);
            }
            left++;
        }
    }
    if(maxLen==Number.MAX_SAFE_INTEGER){
        return "";
    }
    return s.slice(startIdx, startIdx+maxLen);
};

// 检查当前窗口是否已经包含了所有t中所有字符
function check(map){
    for(let v of map.values()){
        if(v>0){
            return false;
        }
    }
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

字符串的排列

题目： 给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。换句话说，s1 的排列之一是 s2 的 子串 。

示例：

输入：s1 = "ab" s2 = "eidbaooo"
输出：true
解释：s2 包含 s1 的排列之一 ("ba").

输入：s1= "ab" s2 = "eidboaoo"
输出：false
1
2
3
4
5
6

题解： 和上一题思路一样，只是这里需要判断滑动窗口的大小刚好等于s1的长度

/**
 * @param {string} s1
 * @param {string} s2
 * @return {boolean}
 */
var checkInclusion = function(s1, s2) {
    let map = new Map();
    for(let i=0;i<s1.length;i++){
        if(map.has(s1[i])){
            map.set(s1[i],map.get(s1[i])+1);
        }else{
            map.set(s1[i], 1);
        }
    }
    let left=0, right=0;
    while(right<s2.length){
        if(map.has(s2[right])){
            map.set(s2[right], map.get(s2[right])-1);
        }
        right++;
        while(check(map)){
            if((right-left)==s1.length){
                return true;
            }
            if(map.has(s2[left])){
                map.set(s2[left], map.get(s2[left])+1);
            }
            left++;
        }
    }
    return false;
};

function check(map){
    for(v of map.values()){
        if(v>0){
            return false;
        }
    }
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

长度最小的子数组

题目： 给定一个含有 n 个正整数的数组和一个正整数 target 。找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
示例：

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
1
2
3

题解： 利用滑动窗口

/**
 * @param {number} target
 * @param {number[]} nums
 * @return {number}
 */
var minSubArrayLen = function(target, nums) {
    let left=0, right=0;
    let sum=0;
    let len = Number.MAX_SAFE_INTEGER;
    while(right<nums.length){
        sum += nums[right];
        right++;
        while(sum>=target){
            len = Math.min(len, right-left);
            sum -= nums[left];
            left++;
        }
        
    }
    return len==Number.MAX_SAFE_INTEGER ? 0 : len;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21