003-无重复字符最长字串（滑动窗口）

无重复字符的最长子串

问题描述

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

示例

• 输入: “abcabcbb”
  输出: 3
  解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
• 输入: “bbbbb”
  输出: 1
  解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
• 输入: “pwwkew”
  输出: 3
  解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。

解决方案

滑动窗口法

这是一个经典的滑动窗口问题。我们可以使用哈希集合来记录当前窗口中的字符，并通过移动窗口的左右边界来寻找最长子串。

function lengthOfLongestSubstring(s) {
    let charSet = new Set();
    let left = 0;
    let maxLength = 0;
    
    for (let right = 0; right < s.length; right++) {
        // 当遇到重复字符时，移动左指针
        while (charSet.has(s[right])) {
            charSet.delete(s[left]);
            left++;
        }
        // 添加当前字符到集合
        charSet.add(s[right]);
        // 更新最大长度
        maxLength = Math.max(maxLength, right - left + 1);
    }
    
    return maxLength;
}

算法分析

• 时间复杂度：O(n)，其中 n 是字符串的长度。每个字符最多被访问两次（一次被加入集合，一次被移除）。
• 空间复杂度：O(min(m, n))，其中 m 是字符集的大小。在最坏情况下，我们需要存储整个字符集

可视化总结

a b c a b c b b
[---]           → "abc" (长度3)
  [---]         → "bca" (长度3)
    [---]       → "cab" (长度3)
        [-]     → "cb" (长度2)
          [ ]   → "b" (长度1)
            [ ] → "b" (长度1)