LeetCode动画 | 3. 无重复字符的最长子串

今天分享一个LeetCode题，题号是3，标题是：无重复字符的最长子串，题目标签：散列表、双指针和字符串。解题思路里有算法动画视频，别漏看了哦，这是最直观最可视化的解题思路，是精粹。

题目描述

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

示例 1:

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

示例 2:

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

解题

这道题最简单的方式是使用暴力法，逐个检查所有的子字符串，剔除掉包含重复字符的字符串，然后计算出所有符合条件的字符串的长度，最后得到最大长度。

虽然能得出正确答案，但是会消耗执行用时和计算空间。俺就优雅一点，不使用暴力。

如何优化或如何选择合适的数据结构，是个问题，没有思路时可以看一下此题的标签：散列表、双指针和字符串。

如果从散列表入手，毫无疑问在写代码过程中用到HashMap，那HashMap跟这道题有什么关系呢？

如果想不出来有什么关系？那也没关系，俺先从直接寻址表入手。如果还没学习过直接寻址表或者散列表可以点击这篇文章<漫画 | 什么是散列表？>。

假定是输入字符串“pwwkew”，我们可以把字符串里每一个字符都看成一个关键字，一个关键字可以指向直接寻址表的一个槽。直接寻址表需要多少个槽可以计算出来，可以通过ASCII码，每一个字符对应着一个十进制位。

ASCII码（美国信息交换标准代码）

对字符串所使用的字符集进行假设，常用的表有如下所示：

int [26] 用于字母 ‘a’ - ‘z’ 或 ‘A’ - ‘Z’
int [128] 用于ASCII码
int [256] 用于扩展ASCII码

看上面题目描述，输入示例都是字母，没有其它的字符，但不排除其它的字符。所以将直接寻址表设定为一个长度为128的数组，值都默认为0，同时将输入字符串转换为字符数组。创建start和end下标，起始下标都为0，maxLen为无重复的最长字串的长度，起始为0，如下图：

start或end下标所指的字符，映射直接寻址表的一个槽（p的ASCII码为112十进制），置为1，如下图：

end下标++，此时的end下标为1，所指向的字符映射直接寻址表中的一个槽（w的ASCII码为119），判断此槽是否为0，如果是，则置为1，end下标继续向下移动，如下图：

end下标++，此时的end下标为1，所指向的字符映射直接寻址表中的一个槽（w的ASCII码为119），判断此槽是否为0，如果不是，意味着字符冲突了，有重复的字符。那就通过移动start下标消除重复的字符。

移动之前先将start下标所指的字符‘p’，‘p’的ASCII码为112，就将直接寻址表下表为112的槽置为0，然后start++，如下图：

在判断end下标所指的字符‘w’，‘w’的ASCII码为119，如上图，查看直接寻址表下表为119的槽，还是为1，则继续移动start下标，重复刚才的步骤的，将直接寻址表下表为119的槽置为0，然后start++，如下图：

这时候判断end下标所指的字符，映射直接寻址表中的一个槽（下表为119），已经置为0了，说明start下标和end下标之间已经没有重复的字符，则放行end下标，end下标继续++。

动画：直接寻址表

http://mpvideo.qpic.cn/0b78ceaacaaanmaj5jjn7rpfaeodaeiqaaia.f10002.mp4?dis_k=81b220c245a1ee4a0698c517896eeaca&dis_t=1581669772

Code

public int lengthOfLongestSubstring(String s) {
    if (s == "") return 0;
    int start = 0, end = 0, maxLen = 0;
    char[] array = s.toCharArray(); // 字符串 转 字符数组
    int[] map = new int[128]; // 作为直接寻址表
    map[array[start]] = 1;
    while (end < s.length()) {
        maxLen = maxLen > (end - start + 1) ? maxLen : (end - start + 1);
        end++;
        if (end == s.length()) break;
        while (map[array[end]] != 0) {
            map[array[start++]] = 0;
        }
        map[array[end]] = 1;
    }
    return maxLen;
}

执行结果

执行用时 : 4 ms, 在所有 Java 提交中击败了91.40%的用户
内存消耗 : 36.7 MB, 在所有 Java 提交中击败了75.59%的用户

用直接寻址表击败了90%以上的用户，说明还是挺快的嘛，但是内存消耗才刚刚击败75%，这就是直接寻址表的缺点。直接寻址表仅适合少量数据的计算。

和直接寻址表对应的是散列表，散列表也是先创建一定长度的数组，HashMap是创建一个长度默认为16的数组，存储链表或者红黑树。

通过散列表方式的代码我就不写了，留给你们做吧?，俺就给个提示。

同样是"pwwkew"作为输入字符串，创建一个HashMap对象，将输入字符串的每一个字符作为键，而值跟直接寻址表一样作为标记。

方式都一样，不过是将直接寻址表改为散列表的数据结构。散列表的执行用时和直接寻址表差不多，而内存消耗会大大降低，从而大大提升性能。

做完这道题之后，提交代码，看一下执行结果，没有达到100%的，说明还有更好的方式在等着你。我也习惯查看排名第一的代码，看一下哪些方式是遗漏了的，或者用了怎么样的数据结构可以更好实现的。

贴上排在第一的代码Code：

public int lengthOfLongestSubstring(String s) {
    if (s == "") return 0;
    char[] cs = s.toCharArray();
    int result = 0, i = 0;
    for (int j = 0; j < s.length(); j++) {
        for (int k = i; k < j; k++) {
            if (cs[j] == cs[k]) {
                i = k + 1;
                break;
            }
        }
        if (j - i + 1 > result)
            result = j - i + 1;
    }
    return result;
}

这段代码没有用直接寻址表，也没有用散列表，而是直接用双指针控制下标。

俺啰嗦一点昂，其实回头看动画视频，把直接寻址表忽略掉，光看右边s和e的下标移动，也是和上面代码一样的，妙啊妙啊。

-END-

长按下图二维码关注公众号，「算法无遗策」持续更新算法