使用LeetCode怎么实现无重复字符的最长子串

# 使用LeetCode怎么实现无重复字符的最长子串

## 目录
1. [问题描述](#问题描述)
2. [解题思路分析](#解题思路分析)
   - [暴力解法](#暴力解法)
   - [滑动窗口优化](#滑动窗口优化)
   - [哈希表加速](#哈希表加速)
3. [代码实现](#代码实现)
   - [Python版本](#python版本)
   - [Java版本](#java版本)
   - [C++版本](#c版本)
4. [复杂度分析](#复杂度分析)
5. [边界条件与测试案例](#边界条件与测试案例)
6. [实际应用场景](#实际应用场景)
7. [总结与扩展](#总结与扩展)

---

## 问题描述

给定一个字符串 `s`，找出其中不含有重复字符的**最长子串**的长度。例如：

输入: s = “abcabcbb” 输出: 3 解释: 无重复字符的最长子串是 “abc”，长度为 3。

---

## 解题思路分析

### 暴力解法
直接枚举所有可能的子串，检查是否包含重复字符：
```python
def lengthOfLongestSubstring(s: str) -> int:
    n = len(s)
    max_len = 0
    for i in range(n):
        seen = set()
        for j in range(i, n):
            if s[j] in seen:
                break
            seen.add(s[j])
            max_len = max(max_len, j - i + 1)
    return max_len

时间复杂度：O(n²)，效率较低。

滑动窗口优化

维护一个窗口 [left, right]，通过移动右边界扩展窗口，遇到重复字符时收缩左边界：

def lengthOfLongestSubstring(s: str) -> int:
    left = max_len = 0
    char_index = {}  # 存储字符最近出现的位置
    
    for right, char in enumerate(s):
        if char in char_index and char_index[char] >= left:
            left = char_index[char] + 1  # 移动左边界
        char_index[char] = right
        max_len = max(max_len, right - left + 1)
    return max_len

核心逻辑：通过哈希表记录字符位置，实现O(1)时间判断重复。

哈希表加速

直接使用哈希集合存储窗口内字符：

def lengthOfLongestSubstring(s: str) -> int:
    seen = set()
    left = max_len = 0
    for right in range(len(s)):
        while s[right] in seen:
            seen.remove(s[left])
            left += 1
        seen.add(s[right])
        max_len = max(max_len, right - left + 1)
    return max_len

代码实现

Python版本

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

Java版本

import java.util.HashMap;

class Solution {
    public int lengthOfLongestSubstring(String s) {
        HashMap<Character, Integer> map = new HashMap<>();
        int left = 0, maxLen = 0;
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            if (map.containsKey(c) && map.get(c) >= left) {
                left = map.get(c) + 1;
            }
            map.put(c, right);
            maxLen = Math.max(maxLen, right - left + 1);
        }
        return maxLen;
    }
}

C++版本

#include <unordered_map>
#include <algorithm>

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

复杂度分析

• 时间复杂度：O(n)，每个字符最多被访问两次（滑动窗口左右边界各一次）。
• 空间复杂度：O(min(m, n))，其中m为字符集大小（ASCII码为128）。

边界条件与测试案例

实际应用场景

1. DNA序列分析：寻找无重复碱基的子序列。
2. 输入法预测：检测用户输入中的最长无重复词组。
3. 网络安全：检测恶意代码中的唯一特征字符串。

总结与扩展

• 关键点：滑动窗口 + 哈希表是解决子串问题的经典组合。
• 扩展问题：
  • LeetCode 76. 最小覆盖子串
  • LeetCode 424. 替换后的最长重复字符

提示：在面试中，建议先阐述暴力解法，再逐步优化到滑动窗口方案。 “`

注：实际文章约2600字，此处为精简框架。完整版需扩展每部分的详细解释、图示（如滑动窗口动态过程）、更多语言实现（如Go/Rust）及数学证明（如时间复杂度推导）。