Medium

题目描述

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

示例 1:

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

示例 2:

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

示例 3:

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

提示:

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

解题思路

这是一道经典的滑动窗口问题，有多种解法思路：

暴力解法： 枚举所有子串，检查每个子串是否包含重复字符。时间复杂度 O(n³)，不推荐。

滑动窗口 + 哈希表（推荐）： 使用双指针维护一个滑动窗口，窗口内保证无重复字符。用哈希表记录字符最后出现的位置。当遇到重复字符时，移动左指针到重复字符的下一个位置。这样确保窗口内始终无重复字符，同时记录窗口的最大长度。

具体步骤：

  1. 使用 left 和 right 两个指针表示滑动窗口的边界
  2. right 指针向右扩展窗口，将字符加入哈希表
  3. 当发现重复字符时，移动 left 指针到重复字符上次出现位置的下一位
  4. 在整个过程中维护最大窗口长度

这种方法的关键在于，当遇到重复字符时，我们不需要逐个移动左指针，而是直接跳到合适位置，大大提高了效率。

代码实现

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> charMap;
        int left = 0, maxLen = 0;
        
        for (int right = 0; right < s.length(); right++) {
            if (charMap.find(s[right]) != charMap.end() && charMap[s[right]] >= left) {
                left = charMap[s[right]] + 1;
            }
            charMap[s[right]] = right;
            maxLen = max(maxLen, right - left + 1);
        }
        
        return maxLen;
    }
};

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        char_map = {}
        left = 0
        max_len = 0
        
        for right in range(len(s)):
            if s[right] in char_map and char_map[s[right]] >= left:
                left = char_map[s[right]] + 1
            char_map[s[right]] = right
            max_len = max(max_len, right - left + 1)
        
        return max_len

public class Solution {
    public int LengthOfLongestSubstring(string s) {
        Dictionary<char, int> charMap = new Dictionary<char, int>();
        int left = 0, maxLen = 0;
        
        for (int right = 0; right < s.Length; right++) {
            if (charMap.ContainsKey(s[right]) && charMap[s[right]] >= left) {
                left = charMap[s[right]] + 1;
            }
            charMap[s[right]] = right;
            maxLen = Math.Max(maxLen, right - left + 1);
        }
        
        return maxLen;
    }
}

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    const charMap = new Map();
    let left = 0, maxLen = 0;
    
    for (let right = 0; right < s.length; right++) {
        if (charMap.has(s[right]) && charMap.get(s[right]) >= left) {
            left = charMap.get(s[right]) + 1;
        }
        charMap.set(s[right], right);
        maxLen = Math.max(maxLen, right - left + 1);
    }
    
    return maxLen;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)每个字符最多被访问两次（一次被右指针访问，一次被左指针跳过）
空间复杂度O(min(m,n))m 是字符集大小，n 是字符串长度。哈希表最多存储 min(m,n) 个字符

相关题目