2025年12月7日，LeetCode Hot 100榜单再次更新，无重复字符的最长子串（LeetCode 3）以41.3%的通过率和中等难度评级，继续稳居字符串类题目榜首。这道题不仅是字节跳动、腾讯等大厂的面试常客，更是理解滑动窗口算法的入门典范。
给定一个字符串 s，请找出其中不含有重复字符的最长子串的长度。例如输入 "abcabcbb" 时，输出应为 3（对应子串 "abc"）；输入 "pwwkew" 时，输出同样为 3（对应子串 "wke"）。注意子串必须是连续的字符序列，这与子序列（可非连续）有本质区别。
滑动窗口算法原理
算法核心思想
滑动窗口本质是动态维护一个边界可调整的区间，通过左右指针的移动来寻找满足条件的最优解。对于本题：
窗口定义：左指针 left 和右指针 right 之间的字符组成当前子串
扩展窗口：右指针向右移动，将新字符加入窗口
收缩窗口：当新字符与窗口内已有字符重复时，左指针移动到重复字符的下一位
记录最值：每次窗口调整后计算长度，更新最大长度
如图所示，对于输入'abcabcbb'，算法通过flag指针记录窗口左边界，i指针遍历字符串：当i=3（字符'a'）时，flag从0移动到1；i=4（字符'b'）时，flag移动到2；i=5（字符'c'）时，flag移动到3；后续移动中窗口长度始终为3，最终得到最长子串长度3。
哈希表优化
为快速判断字符是否重复，我们使用哈希表（或数组）记录字符最后出现的位置。以 Python 为例：
char_map = {}max_len = 0left = 0for right, char in enumerate(s):# 若字符重复且上次出现位置在窗口内，则移动左指针if char in char_map and char_map[char] >= left:left = char_map[char] + 1char_map[char] = rightcurrent_len = right - left + 1max_len = max(max_len, current_len)
多语言代码对比
Python 实现
def lengthOfLongestSubstring(s: str) -> int:char_map = {}max_len = left = 0for right, char in enumerate(s):if char in char_map and char_map[char] >= left:left = char_map[char] + 1char_map[char] = rightmax_len = max(max_len, right - left + 1)return max_len
Java 实现
public int lengthOfLongestSubstring(String s) {int[] lastOccur = new int[128]; // ASCII字符集Arrays.fill(lastOccur, -1);int maxLen = 0, left = 0;for (int right = 0; right < s.length(); right++) {char c = s.charAt(right);if (lastOccur[c] >= left) {left = lastOccur[c] + 1;}lastOccur[c] = right;maxLen = Math.max(maxLen, right - left + 1);}return maxLen;}
Go 实现
func lengthOfLongestSubstring(s string) int {lastOccur := make(map[rune]int)maxLen, left := 0, 0for right, c := range s {if pos, ok := lastOccur[c]; ok && pos >= left {left = pos + 1}lastOccur[c] = rightcurrentLen := right - left + 1if currentLen > maxLen {maxLen = currentLen}}return maxLen}
Rust 实现
use std::collections::HashMap;pub fn length_of_longest_substring(s: String) -> i32 {let mut last_occur = HashMap::new();let mut max_len = 0;let mut left = 0;for (right, c) in s.chars().enumerate() {if let Some(&pos) = last_occur.get(&c) {if pos >= left {left = pos + 1;}}last_occur.insert(c, right);max_len = max_len.max((right - left + 1) as i32);}max_len}
C++ 实现
int lengthOfLongestSubstring(string s) {vector<int> last_occur(128, -1);int max_len = 0, left = 0;for (int right = 0; right < s.size(); right++) {char c = s[right];if (last_occur[c] >= left) {left = last_occur[c] + 1;}last_occur[c] = right;max_len = max(max_len, right - left + 1);}return max_len;}
语言特性对比：
Python/Go/Rust 天然支持哈希表，代码简洁
Java/C++ 使用数组代替哈希表（ASCII字符集），空间效率更高
Rust 的 HashMap 和 C++ 的 vector 都提供了 O(1) 访问复杂度
复杂度分析
时间复杂度
时间复杂度始终为O(n)，每个字符仅被左右指针各访问一次
空间复杂度
哈希表实现：O(min(m, n))，m 为字符集大小（如ASCII为128）
数组实现：O(m)，m 为固定字符集大小（如128或256）
边界条件处理
特殊输入场景
空字符串：直接返回 0
单字符字符串：返回 1
全重复字符：如 "bbbbb"，返回 1
无重复字符：如 "abcde"，返回字符串长度
关键处理代码
def lengthOfLongestSubstring(s: str) -> int:if not s: # 空字符串处理return 0# ... 主体逻辑 ...
常见错误点
左指针未判断重复位置是否在当前窗口内（需 char_map[char] >= left 条件）
哈希表未实时更新字符位置
忽略字符串长度为 0 的边界 case
算法优化与拓展应用
优化方向
字符集优化：对于已知字符范围（如纯英文字母），可用数组代替哈希表
早期终止：当剩余字符数小于当前最大长度时可提前退出
位运算优化：对有限字符集（如小写字母）可用位掩码记录出现位置
实际应用场景
网络爬虫：控制滑动窗口大小抓取连续内容
日志分析：定位最长无重复ID序列
编辑器实现：高亮显示重复字符区间
总结
滑动窗口算法通过动态调整区间边界，将暴力解法的 O(n²) 复杂度优化至 O(n)，完美解决了无重复字符子串问题。本文提供的五种语言实现展示了不同编程范式下的实现技巧，核心都是通过哈希表记录字符位置，配合双指针维护窗口。
掌握该算法后，可进一步挑战 LeetCode 76（最小覆盖子串）、438（找到字符串中所有字母异位词）等进阶题目，这些题目均是滑动窗口思想的延伸应用。记住：复杂问题往往可以通过拆解为「动态区间」问题来高效解决。