当前位置：首页 > news >正文

LeetCode经典题解：3、无重复字符的最长子串

news 2025/7/13 15:57:02

LeetCode入门必刷：无重复字符的最长子串（Java详解+记忆技巧）

在字符串处理类算法题中，“无重复字符的最长子串”是一道高频面试题，也是理解“滑动窗口”思想的绝佳案例。本文用Java实现最优解，并用生活化场景帮你轻松记住核心逻辑，看完就能上手。

一、题目：找到最长的“不重复片段”

问题：给定一个字符串 s，返回其中不包含重复字符的最长子串的长度。

举几个例子直观理解：

输入 s = "abcabcbb" → 输出 3（最长子串是 "abc"）
输入 s = "bbbbb" → 输出 1（只有单个 "b" 不重复）
输入 s = "pwwkew" → 输出 3（最长子串是 "wke" 或 "kew"）

二、最优解法：滑动窗口+哈希表（Java代码）

直接上能通过的代码，核心逻辑用注释标注：

import java.util.HashMap;
import java.util.Map;class Solution {public int lengthOfLongestSubstring(String s) {// 哈希表：记录每个字符最后出现的位置（像个"记事本"）Map<Character, Integer> charMap = new HashMap<>();int maxLen = 0; // 存储最长子串长度int left = 0;   // 滑动窗口的左边界（类似"起点标记"）// 右指针遍历字符串，相当于"终点标记"for (int right = 0; right < s.length(); right++) {char currentChar = s.charAt(right); // 当前字符// 关键：如果当前字符在窗口内重复，就移动左边界到重复位置的右边if (charMap.containsKey(currentChar) && charMap.get(currentChar) >= left) {left = charMap.get(currentChar) + 1;}// 更新记事本：记录当前字符的最新位置charMap.put(currentChar, right);// 计算当前窗口长度，更新最大值maxLen = Math.max(maxLen, right - left + 1);}return maxLen;}
}

三、代码逻辑：用“抓娃娃机”场景理解

把代码逻辑想象成玩抓娃娃机的过程，每个角色对应具体功能，记场景比记代码更有效：

1. 给代码元素“贴标签”

left 和 right 指针：分别是抓娃娃机的“左边界”和“右边界”，两个边界之间的区域就是“当前抓娃娃的范围”（子串）。
charMap 哈希表：像个“记录表”，专门记每个娃娃（字符）最后一次被抓到的位置（索引）。
currentChar：当前正在抓的娃娃（遍历到的字符）。

2. 玩抓娃娃机的流程（核心逻辑）

① 右边界 right 先移动，每次抓一个新娃娃（遍历字符串的每个字符）。
② 抓之前先查“记录表”：

如果这个娃娃之前没抓过，或者上次抓的位置在左边界外面（不在当前范围内），不管它，继续抓。
如果这个娃娃上次抓的位置在当前范围内（charMap.get(currentChar) >= left），说明重复了，必须把左边界 left 移到“上次位置+1”，确保当前范围里没有重复娃娃。
③ 把当前娃娃的位置记到“记录表”里（charMap.put(currentChar, right)）。
④ 每次抓完，算一下当前范围（right - left + 1）的长度，和之前的最大长度比，更新最大值。

四、为什么这样写？—— 从“暴力”到“优化”的思考

刚开始可能会想到“暴力解法”：把所有子串都列出来，检查是否有重复，再找最长的。但这种方法要嵌套两层循环，时间复杂度是 O(n²)，字符串长一点就会超时。

而“滑动窗口+哈希表”的解法：

用 right 指针一次遍历所有字符（O(n) 时间）。
用哈希表（O(1) 查找）快速判断重复，避免重复检查。
左边界 left 只向右移动，不回头，整体效率提升到 O(n)。

五、一句话记住核心逻辑

“右指针扫字符，哈希表记位置，重复就把左指针右移，随时算最长距离。”

拆解一下：

右指针负责“遍历所有字符”；
哈希表负责“记住每个字符最后出现的位置”；
左指针负责“遇到重复时右移，保证窗口内无重复”；
每次移动后计算“当前窗口长度”，更新最大值。

六、Java代码实战小贴士

哈希表可以用数组优化：如果字符串只包含 ASCII 字符（比如英文字母、数字），可以用 int[128] 代替 HashMap，效率更高（数组访问比哈希表快）：

public int lengthOfLongestSubstring(String s) {int[] lastPos = new int[128]; // 存储字符最后出现的位置，初始为0Arrays.fill(lastPos, -1); // 初始化为-1（表示未出现）int maxLen = 0;int left = 0;for (int right = 0; right < s.length(); right++) {char c = s.charAt(right);if (lastPos[c] >= left) {left = lastPos[c] + 1;}lastPos[c] = right;maxLen = Math.max(maxLen, right - left + 1);}return maxLen;
}