JS_LeetCode08：无重复字符的最长子串

image-20250515221146792

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

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

滑动窗口

本质上也是双指针，它们俩维护了一个窗口，并且窗口可以滑动，也可以伸缩。

它是动态维护子区间的一种算法技巧。

这道题怎么思考呢？

首先left和right指针放在字符串的起始位置，准备出发！谁出发？right指针负责探索！去将满足条件的字符收入窗口，所以right开始出发。但是，我们要怎么判断right遇到的字符是否满足条件呢？利用哈希表记录！

哈希表

JS里面的Set和Map的底层都是哈希表，插入元素、删除元素或判断元素是否存在的时间复杂度都是O(1)。

1
2
3
4
const set = new Set()
set.add(1)
set.delete(1)
set.has(1)
1
2
3
4
const map = new Map()
map.set('name','anan')
map.delete('name')
map.has('name')

如果你用数组去记录的话，查找是线性的，性能不行。

1
2
3
4
consr arr = [1,2,3]
arr.push(4)
arr.pop()
arr.includes(4)

ok，哈希表记录遇到的字符，键是字符，值是字符所在的索引。每次right去判断当前字符是否已经在map中了。

这时候就分为两种情况：

  • 在map中

    代表该字符重复了。此时，left指针发挥作用！left要维护窗口的纯洁性呀！于是left去查map里面的该元素的索引，跳到索引的下一位！

    是这样吗？陷阱！小心！首先map记录的字符肯定是right来时的路，但不一定是left来时的路，可能是left前面的，也可能是left后面的。那影响滑动窗口纯洁性的只能是left前面的字符。所以需要判断查到的索引和left自身的索引，取它们中更大的一个作为滑动窗口的新起点。

  • 不在map中

    right指针辛苦一下，记录字符到map，Thanks♪(･ω･)ﾉ并且继续前进！

对了！我们需要知道最长不重复子串的长度对吧？所以窗口的长度要保持更新！

什么时候结束呢？right指针走到了字符串的尽头。探险结束！

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    let left = 0
    let right = 0
    let map = {}
    let maxLen = 0
    while (right < s.length){
        if (s[right] in map){
            left = Math.max(map[s[right]] + 1,left)
        }
        map[s[right]] = right
        maxLen = Math.max(maxLen,right-left+1)
        right ++
    }
    return maxLen
};