常用算法 — 滑动窗口

滑动窗口也是一种双指针算法,但是滑动窗口特别强调窗口向一个方向滑动,看起来简单,但是却属于最难的一种双指针技巧,力扣上的题一般都是中等或困难难度。首要问题是识别什么样的问题需要滑动窗口解决,最常见的题型:子串问题。

子串问题 #

子串问题中,除了需要有 left 和 right 双指针,还需要计算(或比较)滑动窗口中的内容,常见的做法是维护一个(甚至更多)哈希表,需要更多哈希表的原因是一个维护窗口内的计数,另一个需要维护整个子串的计数器,用于互相比较。

因为每个字符都能够转换成 ASCII 码,除了哈希表有时维护一个长度为 26 的数组也可以(但要看题目是否只有小写字母),灵活考虑。比如 js 中虽然 map.size 很好用,但是给 map 的值做 ++ 运算却很麻烦,go 用 map 却很简单,所以哪个方便用哪个。

package main

import "fmt"

func main() {
	m := make(map[string]int)
	m["a"]++
	fmt.Println(m["a"]) // 1
	fmt.Println(m["c"]) // 0
}

滑动窗口解子串问题的核心思想:

  1. 维护左右两个指针,两指针之间就是窗口内容。
  2. 右指针向右滑动,直到窗口的子串符合满足题目要求。
  3. 停止右指针向右滑动,开始将左指针向右滑动,每次增加 left,都要更新窗口计数器内容。
  4. 重复 2 和 3,直到右指针到达尽头。

76. 最小覆盖子串(困难)这道题解的结构非常有代表性,而且比较难的地方也在于题目要求大小写都会包括,故只能用哈希表来保存窗口。

var minWindow = function (s, t) {
    let need = new Map(),
        window = new Map();
    let left = 0,
        right = 0;

    let valid = 0,
        start = 0;
    let len = Infinity;

    for (let i = 0; i < t.length; i++) {
        let curr = t[i];
        if (need.has(curr)) {
            let v = need.get(curr);
            need.set(curr, ++v);
        } else {
            need.set(curr, 1);
        }
    }

    while (right < s.length) {
        let c = s[right];
        right++;

        if (need.has(c)) {
            if (window.has(c)) {
                let v = window.get(c);
                window.set(c, ++v);
            } else {
                window.set(c, 1);
            }
            if (window.get(c) == need.get(c)) {
                valid++;
            }
        }
        while (valid === need.size) {
            if (right - left <= len) {
                start = left;
                len = right - left;
            }

            let d = s[left];
            left++;

            if (need.has(d)) {
                let v = window.get(d);
                if (window.get(d) === need.get(d)) {
                    valid--;
                }
                window.set(d, --v);
            }
        }
    }

    if (len === Infinity) {
        return "";
    } else {
        return s.substr(start, len);
    }
};

console.log(minWindow("ADOBECODEBANC", "ABC"));

567. 字符串的排列 和上面的结构一样,并且改为了 Array 实现。

var checkInclusion = function(s1, s2) {
    let need = new Array(26).fill(0)
    let window = new Array(26).fill(0)
    let left = 0, right = 0
    let ac = 'a'.charCodeAt()

    for (let i = 0; i < s1.length; i ++) {
        need[s1[i].charCodeAt() - ac] ++
    }

    while (right < s2.length) {
        let curr = s2[right]
        right++

        if (need[curr.charCodeAt() - ac] > 0) {
            window[curr.charCodeAt() - ac] ++
        }

        while(right - left >= s1.length) {
            if (need.toString() === window.toString()) {
                return true
            }
            let head = s2[left]
            left++
            if (need[head.charCodeAt()- ac] > 0) {
                window[head.charCodeAt() - ac] --
            }
        }
    }
    return false
};

438. 找到字符串中所有字母异位词

使用 Array 实现,个人感觉比 Map 要舒服点,也不需要 valid 计数了。

var findAnagrams = function(s, p) {
    let need = new Array(26).fill(0)
    let window = new Array(26).fill(0)

    let left = 0, right = 0
    let ac = 'a'.charCodeAt()
    let ret = []

    for (let i = 0; i < p.length; i++) {
        need[p[i].charCodeAt() - ac]++
    }

    while(right<s.length) {
        let curr = s[right]
        right ++

        if (need[curr.charCodeAt() - ac] > 0) {
            window[curr.charCodeAt() - ac]++
        }

        if(right - left >= p.length) {
            if (window.toString() === need.toString()) {
                ret.push(left)
            }
            let head = s[left]
            left ++
            if (need[head.charCodeAt() - ac] > 0){
                window[head.charCodeAt() - ac] --
            }
        }
    }
    return ret
};

另外两个数组可以考虑试图优化成一个数组,一加一减的思路。

总结一下必备的要素:

  1. need 符合要求的结果
  2. windows 当前窗口的结果
  3. leftright 移动的窗口两边

3. 无重复字符的最长子串(必会)

func lengthOfLongestSubstring(s string) int {
    left := 0
    right := 0
    window := make(map[string]int)
    ret := 0
    for(right < len(s)) {
        c := string(s[right])
        right ++
        window[c] ++

        for (window[c] > 1) {
            d := string(s[left])
            left++
            window[d] --
        }
        ret = max(ret, right - left)
    }
    return ret
}

参考 #

https://labuladong.github.io/algo/2/19/26/

本文共 1072 字,上次修改于 Oct 12, 2022
相关标签: 算法