LC3. 无重复字符的最长子串

题目描述

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。 示例 1: 输入: s = "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。 示例 2: 输入: s = "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。 示例 3: 输入: s = "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。 提示： 0 <= s.length <= 5 * 10^4 s 由英文字母、数字、符号和空格组成

题目解析

题目在说什么

题目给了你一个字符串，比如 "abcabcbb"，你要找出其中连续的一段（子串），这段里面不能有重复的字符，然后返回这个子串最长能有多长。

比如 "abcabcbb" 里，最长的无重复子串是 "abc"，长度是 3。注意必须是连续的，不能跳着选，比如 "ab" 是子串，但 "ac" 不是，因为中间跳过了 b。

思路是怎么来的

想象你在看一个电影的字幕，字幕是一行字从左到右滚动。你想找出一段没有重复字的连续字幕，而且越长越好。

你可能会这样做：

• 用一根手指（左指针）指着字幕开头，另一根手指（右指针）慢慢往右移动。
• 每移动一格，看看新出现的字有没有和之前看过的字重复。
• 如果没重复，就继续往右，记录当前这段的长度。
• 如果重复了，就把左手指往右挪，直到把重复的那个字“挤出去”，然后再继续。

这就是滑动窗口的思路：一个窗口（左右指针之间的部分）在字符串上滑动，窗口里永远是没有重复字符的。我们要找的就是窗口最大能有多大。

代码逐步拆解

我们来看参考代码，一步步拆开讲。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        // 1. 准备工具：一个记录最大长度的变量，一个记录窗口里有哪些字符的哈希表
        int maxLen = 0;
        HashSet<Character> hash = new HashSet<Character>();

        // 2. 窗口左端 start 从 0 开始，右端 end 用 for 循环从 0 到字符串末尾
        int start = 0;
        for (int end = 0; end < s.length(); end++) {

            // 3. 如果新字符已经在窗口里了（重复了），就要移动左端，直到把重复的字符踢出去
            while (hash.contains(s.charAt(end))) {
                // 把左端字符从哈希表里移除
                hash.remove(s.charAt(start));
                // 左端向右移动一格
                start++;
            }

            // 4. 现在窗口里没有重复字符了，把新字符加进去
            hash.add(s.charAt(end));

            // 5. 更新最大长度：当前窗口长度是 end - start + 1
            maxLen = Math.max(maxLen, end - start + 1);
        }

        // 6. 返回结果
        return maxLen;
    }
}

关键步骤解释：

• 为什么用哈希表？

哈希表能快速判断一个字符是否已经在窗口里（contains 方法很快），而且能方便地添加和删除字符。

• 为什么重复时要移动左端？

因为窗口里不能有重复字符。如果新字符和窗口里某个字符重复了，就必须把那个重复的字符以及它左边的所有字符都移出窗口，才能保证新字符加入后窗口依然无重复。移动左端就是做这件事。