题目

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

思路

  1. 暴力循环
    定义两个 for，第一个 for 顺序遍历，第二个 for 每次从头开始顺序检查，这样即可拿到最长长度，时间复杂度为 O(n^2)。
  2. map 结构
    定义一个 while，利用一个 map 记录遍历到的字符，利用内部 while 进行检查是否有重复字符

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function lengthOfLongestSubstring(s: string): number {

    let l = 0, r = 0, res = 0, len = s.length;
    let map = new Map<string, number>();

    while (r < len) {
        let char = s[r++], count = (map.get(char) || 0) + 1;
        map.set(char, count);

        while (map.get(char) > 1) {
            const left = s[l++]
            map.set(left, map.get(left) - 1)
        }
        res = Math.max(res, r - l); // 此时的r属于后一位，不需要+1
    }

    return res;

};

其他