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

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]; // 存储字符最后出现的位置，初始为0
    Arrays.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;
}

特殊情况处理：空字符串（s = ""）返回 0，单字符（s = "a"）返回 1，这些代码都能自动处理。

七、练手小例子

拿 s = "abba" 走一遍流程，加深理解：

right=0（'a'）：哈希表记 a:0，窗口 [0,0]，长度 1，max=1。
right=1（'b'）：哈希表记 b:1，窗口 [0,1]，长度 2，max=2。
right=2（'b'）：哈希表中 b 上次位置是 1（在窗口内），left 移到 2，窗口 [2,2]，长度 1，max 还是 2。
right=3（'a'）：哈希表中 a 上次位置是 0（在 left=2 外面），窗口 [2,3]，长度 2，max 保持 2。

最终结果是 2，正确。

通过生活化场景理解滑动窗口，再记住那句核心口诀，这道题就很难忘记了。下次遇到类似“找最长不重复片段”的问题，就能直接套用这个思路啦。

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