数据结构与算法之字典: Leetcode 3. 无重复字符的最长子串 (Typescript版)

无重复字符的最长子串

• https://leetcode.cn/problems/longest-substring-without-repeating-characters/

描述

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

示例 1

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
1
2
3

示例 2

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
1
2
3

示例 3

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
1
2
3
4

提示

• 0 <= s.length <= 5 * $10^4$
• s 由英文字母、数字、符号和空格组成

算法实现

1 ）双指针滑动窗口遍历

function lengthOfLongestSubstring(s: string): number {
    let l = 0;
    let res = 0;
    // 用于标记重复字符的字典结构
    const map = new Map();
    for(let r = 0; r < s.length; r++) {
        if(map.has(s[r]) && map.get(s[r]) >= l) {
            // 字典中存在
            l = map.get(s[r]) + 1;
        }
        res = Math.max(res, r - l + 1);
        map.set(s[r], r); // 字典更新最新的右指针
    }
    return res;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

• 先找出所有不包含重复字符的子串，找出长度最大那个子串，返回其长度即可
• 用双指针维护一个滑动窗口，用来剪切子串
• 不断移动右指针，遇到重复字符，就把左指针移动到重复字符的下一位
• 在输入：“abcabcbb”
• 即左指针指向a(下标为0), 右指针指向c的时候，再移动一位, 右指针指向a(下标为3)的时候
• 左指针移动一位到b(下标为1)
• 移动过程中，记录所有窗口的长度，并返回最大值

2 ）暴力遍历

function lengthOfLongestSubstring(s: string): number {
  const len = s.length;
  let max = 0;

  for (let i = 0; i < len; i++) {
    const set = new Set();
    let maxLen = 0;
    let j = i;
    while (j < len && !set.has(s[j])) {
      set.add(s[j]);
      maxLen++;
      j++;
    }
    max = Math.max(max, maxLen);
  }
  return max;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

• 使用set集合来确定字符串的连续型，并暴力枚举各种符合情况
• 这种算法不推荐