【字符串】滑动窗口

[miracles1919]

参考: 我写了套框架，把滑动窗口算法变成了默写题

先上模板，时间复杂度 O(n)

// 伪代码
let left = 0, right = 0
while(right < str.length) {
  window.add(s[right])
  right++

  while(window needs shrink) {
    window.remove(str[left])
    left++
  }
}

[miracles1919]

3. 无重复字符的最长子串

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {
    let left = 0, right = 0
    let window = {}
    let res = 0

    while (right < s.length) {
        const c = s[right]
        if (window[c] === undefined) window[c] = 0
        window[c]++
        right++

        while (window[c] > 1) {
            window[s[left]]--
            left++
        }
        res = Math.max(res, right - left)
    }

    return res
};

优化空间：利用哈希表记录字符位置，遇到重复时直接修改 left

var lengthOfLongestSubstring = function (s) {
    let left = 0, right = 0
    let window = {}
    let res = 0
    let map = {}

    while (right < s.length) {
        const c = s[right]
        if (window[c] === undefined) window[c] = 0
        window[c]++

        if (window[c] > 1) {
            if (map[c] >= left) {
                left = map[c] + 1
            }
        }

        map[c] = right
        right++

        res = Math.max(res, right - left)
    }

    return res
};

另一种形式的滑动窗口

var lengthOfLongestSubstring = function (s) {
    let res = 0
    let window = []
    for (let c of s) {
        while (window.includes(c)) {
            window.shift()
        }
        window.push(c)
        res = Math.max(res, window.length)
    }

    return res
};

[miracles1919]

567. 字符串的排列

• 当 window[c] === need[c] 时，说明 c 字符满足个数，count + 1
• 当 count === need.size 时，说明窗口满足条件

/**
 * @param {string} s1
 * @param {string} s2
 * @return {boolean}
 */
var checkInclusion = function (s1, s2) {
    let left = 0, right = 0
    let need = {}
    let window = {}
    for (let c of s1) {
        if (need[c] === undefined) need[c] = 0
        need[c]++
    }
    const needLen = Object.keys(need).length
    let count = 0
    while (right < s2.length) {
        const c = s2[right++]

        if (need[c]) {
            if (window[c] === undefined) window[c] = 0
            window[c]++
            if (window[c] === need[c]) count++
        }

        while (right - left >= s1.length) {
            if (count === needLen) return true

            const c = s2[left++]
            if (need[c]) {
                if (window[c] === need[c]) count--
                window[c]--
            }
        }
    }

    return false
};

[miracles1919]

76. 最小覆盖子串 hard

• 当 window[c] === need[c] 时，说明 c 字符满足个数，count + 1
• 当 count === need.size 时，说明窗口满足条件

/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
var minWindow = function (s, t) {
    let left = 0, right = 0
    let window = {}
    let need = {}
    let count = 0
    let minLen = Infinity
    let start = 0

    for (let c of t) {
        if (need[c] === undefined) need[c] = 0
        need[c]++
    }
    const needLen = Object.keys(need).length

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

        if (need[c]) {
            if (window[c] === undefined) window[c] = 0
            window[c]++
            if (window[c] === need[c]) count++
        }

        // 收缩窗口
        while (count === needLen) {
            if (right - left < minLen) {
                // 更新最小子串
                start = left
                minLen = right - left
            }

            const c = s[left]
            left++
            if (need[c]) {
                if (window[c] === need[c]) count--
                window[c]--
            }
        }
    }

    return minLen === Infinity ? '' : s.substr(start, minLen)
};

[miracles1919]

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

/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
var findAnagrams = function (s, p) {
    let left = 0, right = 0
    let res = []
    let need = {}
    let window = {}
    let count = 0

    for (let c of p) {
        if (need[c] === undefined) need[c] = 0
        need[c]++
    }

    const needLen = Object.keys(need).length

    while (right < s.length) {
        const c = s[right++]
        if (need[c]) {
            if (window[c] === undefined) window[c] = 0
            window[c]++

            if (window[c] === need[c]) count++
        }

        while (right - left >= p.length) {
            if (count === needLen) { 
                res.push(left)
            }

            const c = s[left++]
            if (need[c]) {
                if (window[c] === need[c]) count--
                window[c]--
            }
        }
    }

    return res
};