专栏首页算法无遗策LeetCode动画 | 3. 无重复字符的最长子串

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-

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

本文分享自微信公众号 - 算法无遗策(gh_6519e8c0cb55),作者:我脱下短袖

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-01-28

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode动画 | 17.电话号码的字母组合

    今天分享一个LeetCode题,题号是17,题目是电话号码的字母组合,题目标签是字符串和回溯算法。

    我脱下短袖
  • LeetCode | 使用双指针解决11号题

    第4题号还有二分查找和分治算法,算法比较复杂。那我就接着做下一道题号,第11题号。

    我脱下短袖
  • 视频动画 | 什么是鸡尾酒排序?

    鸡尾酒排序其实就是冒泡排序的变形,它的时间复杂度和冒泡排序一样,都是O(n^2),比快速排序要慢不少。

    我脱下短袖
  • kafka sql入门

    问题导读 1.kafka sql与数据库sql有哪些区别? 2.KSQL有什么作用? 3.KSQL流和表分别什么情况下使用?

    用户1410343
  • Visual Studio项目版本转换器(c#项目版本转换器 v1.0)

    Visual Studio项目版本转换器(c#项目版本转换器 v1.0) 使用截图: ? 下载地址:http://files.cnblogs.com/stone...

    Java中文社群_老王
  • 都说lncRNA只有部分具有polyA尾结构,请证明

    但是慢慢的科研热点转到了lncRNA,虽然lncRNA只有部分具有polyA尾结构,但也意味着公共数据库里面海量的mRNA-seq表达矩阵里面,都是可以提取到l...

    生信技能树
  • TypeScript学习笔记之基础类型

    从今天开始学习typescript了,记录ts学习点滴,最后,使用ts结合nodejs开发后端应用,一起共勉吧: typescript最新版本2.6,所有演示代...

    用户1141560
  • 腾讯文旅与欧洲旅游委员会签订战略合作协议 | 数字文旅周报30期(9.16-9.22)

    ? 腾讯文旅与欧洲旅游委员会 签订战略合作协议 2019年9月 20日下午,欧洲旅游委员会(ETC)与腾讯文旅签订了战略合作协议。 双方致力于共同提升中国...

    腾讯文旅
  • 《全球智慧旅游城市报告》发布 分享智慧旅游发展新经验 | 数字文旅周报28期(9.2-9.8)

    ? 《全球智慧旅游城市报告》发布 分享智慧旅游发展新经验 9月3日,2019世界旅游城市联合会赫尔辛基香山旅游峰会正式开幕。在开幕式上,世界旅游城市联合会...

    腾讯文旅
  • 百名记者走进全国首家腾讯联通智慧生活馆 体验5G新技术| 数字文旅周报20期(7.8-7.14)

    ? 百名记者走进全国首家腾讯联通智慧生活馆 体验5G新技术 7月5日上午,“文明与城市共成长——2019全国融媒体南昌行”采访团一行来到位于南昌高新区的全国首...

    腾讯文旅

扫码关注云+社区

领取腾讯云代金券