内容纲要
🟣最长无重复子串（Longest Substring Without Repeating Characters）
✅ 算法介绍
题目：给定一个字符串 s，请你找出其中不含有重复字符的最长子串的长度。
核心思路：
滑动窗口（Sliding Window）+ 哈希表（或数组）
窗口用两个指针 left 和 right 控制，哈希表记录字符上一次出现的位置，保证窗口内没有重复字符。
🟢 常见变体
| 变体 | 描述 |
|---|---|
| LC3 | 最长无重复子串的长度 |
| LC159 | 至多两个不同字符的最长子串 |
| LC340 | 至多 K 个不同字符的最长子串 |
| LC76 | 最小覆盖子串（最小滑动窗口） |
| LC567 | 字符串的排列 |
🔥 出现频率
⭐⭐⭐⭐
⏱️ 时间 & 空间复杂度
| 类别 | 复杂度 |
|---|---|
| 时间复杂度 | O(n) |
| 空间复杂度 | O(n) |
🐍 Python 实现
def length_of_longest_substring(s: str) -> int:
left = 0
max_len = 0
used = {}
for right in range(len(s)):
if s[right] in used and used[s[right]] >= left:
left = used[s[right]] + 1
used[s[right]] = right
max_len = max(max_len, right - left + 1)
return max_len☕ Java 实现
public int lengthOfLongestSubstring(String s) {
int left = 0, maxLen = 0;
Map<Character, Integer> map = new HashMap<>();
for (int right = 0; right < s.length(); right++) {
if (map.containsKey(s.charAt(right)) && map.get(s.charAt(right)) >= left) {
left = map.get(s.charAt(right)) + 1;
}
map.put(s.charAt(right), right);
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}🐹 Go 实现
func lengthOfLongestSubstring(s string) int {
left, maxLen := 0, 0
used := make(map[byte]int)
for right := 0; right < len(s); right++ {
if idx, ok := used[s[right]]; ok && idx >= left {
left = idx + 1
}
used[s[right]] = right
if maxLen < right-left+1 {
maxLen = right - left + 1
}
}
return maxLen
}🌐 JavaScript 实现
function lengthOfLongestSubstring(s) {
let left = 0, maxLen = 0;
const used = new Map();
for (let right = 0; right < s.length; right++) {
if (used.has(s[right]) && used.get(s[right]) >= left) {
left = used.get(s[right]) + 1;
}
used.set(s[right], right);
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}🧵 C 实现
int lengthOfLongestSubstring(char * s){
int used[128] = {0}, left = 0, maxLen = 0;
for (int right = 0; s[right]; right++) {
if (used[s[right]] > left) {
left = used[s[right]];
}
used[s[right]] = right + 1;
if (maxLen < right - left + 1) {
maxLen = right - left + 1;
}
}
return maxLen;
}🧠 C++ 实现
int lengthOfLongestSubstring(string s) {
unordered_map<char, int> used;
int left = 0, maxLen = 0;
for (int right = 0; right < s.size(); right++) {
if (used.count(s[right]) && used[s[right]] >= left) {
left = used[s[right]] + 1;
}
used[s[right]] = right;
maxLen = max(maxLen, right - left + 1);
}
return maxLen;
}🌍 语言对照表（核心语句）
| 功能 | Python | Java | Go | JavaScript | C | C++ |
|---|---|---|---|---|---|---|
| 滑动窗口 | left, right |
left, right |
left, right |
left, right |
left, right |
left, right |
| 记录字符位置 | dict |
HashMap |
map |
Map |
int[] |
unordered_map |
| 更新左指针 | left = used[char] + 1 |
同左 | 同左 | 同左 | 同左 | 同左 |
| 最大长度更新 | max() |
Math.max() |
if + manual |
Math.max() |
if + manual |
max() |
🧩 常见优化点
- 若只涉及 ASCII 字符，可以用数组替代哈希表，提升常数性能。
- 滑动窗口边界处理要小心，不要遗漏
left = used[char] + 1。 - C 和 C++ 注意下标偏移，
used[s[right]] = right + 1是防止0初始值混淆。 - 面试时如果能主动提到用数组优化空间，容易加分。
✨ 小技巧
while写法同样常见，但面试推荐用for，因为更清晰。- 拓展应用：该滑窗结构可直接套在「最长满足某条件的连续子串」类题目。
left <= right作为滑动窗口的标准边界写法。
