# 使用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 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 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; } } #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; } }; | 测试案例 | 预期输出 | 说明 |
|---|---|---|
"" | 0 | 空字符串 |
"bbbbb" | 1 | 全部重复字符 |
"pwwkew" | 3 | 最长子串为"wke" |
"abcabcbb" | 3 | 经典案例 |
" " | 1 | 空格字符 |
提示：在面试中，建议先阐述暴力解法，再逐步优化到滑动窗口方案。 “`
注：实际文章约2600字，此处为精简框架。完整版需扩展每部分的详细解释、图示（如滑动窗口动态过程）、更多语言实现（如Go/Rust）及数学证明（如时间复杂度推导）。
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
