关注公众号
原创
二哥的 LeetCode 刷题笔记：003.无重复字符的最长子串

《二哥的 LeetCode 刷题笔记》真的经典。 ------------------------by鲁迅

题意

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

示例

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

难度

中等

分析1

看完这道题目的描述，脑袋里面要先搞清楚几个概念：

  • 什么是子串？
  • 什么是最长子串？
  • 什么是不含重复字符的最长子串？

这三个概念搞清楚，才能去写题解，对吧？

什么是子串？拿题目给出的示例来说，abcabcbb，它的子串有：

a、b、c、a、b、c、b、b 这种单个子串
ab、bc、ca、cb、bb 这种两个字符组成的子串
abc、bca、cab、bcb、cbb 这种三个字符组成的子串
abca、bcab、cabc、abcb 这种四个字符组成的子串
abcab、bcabc、cabcb、abcbb 这种五个字符组成的子串
abcabc、bcabcb、cabcbb 这种六个字符组成的子串
abcabcb bcabcbb 这种七个字符组成的子串
abcabcbb 这种八个字符组成的子串

什么是最长子串？

就是子串中字符个数最多的那个子串，比如上面的例子中，abcabcbb就是最长子串。

什么是不含重复字符的最长子串？

就是最长子串中没有重复字符的那个子串，abcabcbb 虽然是最长子串，但有重复字符 a、b、c，所以不是不含重复字符的最长子串。

abcabcb 也不是，因为有重复字符 a、b、c。

abcabc 也不是，因为有重复字符 a、b、c。

abcab 也不是，因为有重复字符 a、b。

abca 也不是，因为有重复字符 a。

排除到最后，你会发现，不含重复字符的最长子串有这么几个：

abc、bca、cab

OK，答案出来了，长度为 3。

借着这个思路，我们直接来暴力解题。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int res = 0; // 用于存储最长子串的长度
        // 外层循环，从字符串的第一个字符开始
        for (int i = 0; i < s.length(); i++) {
            boolean[] book = new boolean[300]; // 布尔数组，用于标记字符是否出现过

            // 内层循环，从当前字符向前遍历
            for (int j = i; j >= 0; j--) {
                // 如果字符已经在子串中出现过，结束内层循环
                if (book[s.charAt(j)]) 
                    break;

                // 标记当前字符为出现过
                book[s.charAt(j)] = true;
                // 更新最长子串的长度
                res = Math.max(res, i - j + 1);
            }
        }
        return res; // 返回最长子串的长度
    }
}

两层循环，第一层循环用来确定起始位置，第二层循环用来确定结束位置，向前去找最长的子串，如果字符出现过，我们就标记它为 true，并且计算最长子串的长度。

①、题目说 s 由英文字母、数字、符号和空格组成，那么它很可能是 ASCII 码字符集，在 ASCII 字符集中，有 128 个不同的字符，这包括了大小写英文字母（52个）、数字（10个）、标点符号和特殊字符（如空格、制表符等），以及一些控制字符。

那为了节省空间，数组 book 的长度其实可以声明为 128，而不是 300。

boolean[] book = new boolean[128]; // 足以覆盖所有 ASCII 字符

当然了，笔试的时候时间紧张，如果没办法考虑周全的话，300 肯定是一个保险的方案，确保出现的字符都能够容纳得下。

②、i - j + 1 用来计算子串的长度，这里的 i 是外层循环的循环变量，j 是内层循环的循环变量，i - j + 1 就是子串的长度。

  • i 是子串末尾字符的索引。
  • j 是子串起始字符的索引。
  • i - j 是子串起始和结束字符之间的距离（即子串的长度减去 1）。
  • 加上 1 (i - j + 1) 是为了包含起始字符在内的整个子串的长度。

在例子 "abcabcbb" 中，当我们考虑以第一个 'b'（索引 1）结尾的子串时：

  • 当 i = 1（'b' 的位置）和 j = 1（仍然是 'b' 的位置）时，i - j + 1 = 1，表示子串 "b" 的长度。
  • 当 i = 1 和 j = 0（'a' 的位置）时，i - j + 1 = 2，表示子串 "ab" 的长度。

当字符串 s = "abcabcbb" 时，我们用该题解来模拟一下整个题解的过程。

  1. 初始化：最长子串长度 res = 0。

  2. 开始外层循环：逐字符遍历字符串 s。

    • i = 0（字符 'a'）：

      • 初始化 book 数组，其中所有值均为 false。
      • 内层循环：从 j = 0 开始向前遍历。
        • 检查 'a' 是否已经出现过（book[s.charAt(0)]），结果为 false。
        • 标记 'a' 为出现过（book['a'] = true）。
        • 更新 res 为 max(res, i - j + 1)，即 max(0, 0 - 0 + 1) = 1。
        • 退出内层循环。
        • 注意：这里的子串是 "a"，长度为 1。

    • i = 1（字符 'b'）：

      • 初始化 book 数组，其中所有值均为 false。
      • 内层循环：从 j = 1 开始向前遍历。
        • 检查 'b' 是否已经出现过，结果为 false。
        • 标记 'b' 为出现过。
        • 更新 res 为 max(1, 1 - 1 + 1) = 1。
      • 内层循环：j = 0。
        • 检查 'a' 是否已经出现过，结果为 false。
        • 标记 'a' 为出现过。
        • 更新 res 为 max(1, 1 - 0 + 1) = 2。
        • 退出内层循环。
        • 注意：这里的子串是 "ab"，长度为 2。

    • i = 2（字符 'c'）：

      • 初始化 book 数组，其中所有值均为 false。
      • 内层循环：从 j = 2 开始向前遍历。
        • 检查 'c' 是否已经出现过，结果为 false。
        • 标记 'c' 为出现过。
        • 更新 res 为 max(1, 2 - 2 + 1) = 1。
      • 内层循环：j = 1
        • 检查 'b' 是否已经出现过，结果为 false。
        • 标记 'b' 为出现过。
        • 更新 res 为 max(1, 2 - 1 + 1) = 2。
      • 内层循环：j = 0
        • 检查 'a' 是否已经出现过，结果为 false。
        • 标记 'a' 为出现过。
        • 更新 res 为 max(2, 2 - 0 + 1) = 3。
        • 退出内层循环。
        • 注意：这里的子串是 "abc"，长度

4人已点赞