题目

题解

队列

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    const len = s.length
    const queue = []
    const strArr = [...s]
    let longest = 0
    for (let i = 0; i < len; i++) {
        let existIdx = queue.indexOf(strArr[i])
        if (existIdx > -1) {
            let start = 0
            while (start <= existIdx) {
                queue.shift()
                start++
            }
        }
        queue.push(strArr[i])
        longest = Math.max(queue.length, longest)
    }
    return longest
};

滑动窗口

滑动窗口是字符串或者数组中常见的一种抽象概念，窗口指的是在数组或者字符串中由开始索引、结束索引所组成的一系列元素的集合([l, r) 左闭右开)。而滑动指的是窗口的边界l 、r可以左右移动。比如如果窗口往右移动1位，则变成[l+1, r+1)。

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    let len = s.length
    // 左边界索引
    let l = 0
    // 右边界索引
    let r = 0
    let max = 0
    const subStr = [...s]
    const set = new Set()
    while (l < len && r < len) {
        if (!set.has(subStr[r])) {
            set.add(subStr[r++])
            max = Math.max(max, r - l)
        } else {
            set.delete(subStr[l++])
        }
    }
    return max
};

这个case最坏情况时间复杂度是O(2n)，每个字符都恰好被l,r访问一次。

进阶版滑动窗口

不管是之前的队列版本、还是上述的滑动窗口版本，有个地方可以优化，时间复杂度最坏情况下是O(2n)，每个字符恰好被l、r访问一次。只所以出现这个问题是因为之前如果一个元素s[k]出现在窗口[l, r)之间，我们会不断从Set删除前面元素，并通过l++来进行缓慢的左边界移动导致元素被重复访问。那么其实这步是可以加速的。

优化版就是解决上述问题，也就是说，如果s[k]在窗口[l, r)之间出现重复元素k`，那么我们直接跳过[l, k ]，把l变成k+1。

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    const len = s.length
    const map = new Map()
    const strArr = [...s]
    let max = 0
    for (let l = 0, r = 0; r < len; r++) {
        if (map.has(strArr[r])) {
            l = Math.max(l, map.get(strArr[r]))
        }
        // r + 1 是为了方便重复时候直接跳到下一个位置
        map.set(strArr[r], r + 1)
        max = Math.max(max, r - l + 1)
    }
    return max
};

ps: 欢迎关注我的公众号 xyz编程日记，觉得不错的帮忙点个👍，点个在看。