专栏首页HelloCode开发者学习平台BAT面试算法进阶(4)-无重复字符的最长子串

BAT面试算法进阶(4)-无重复字符的最长子串

上篇文章分享的是暴力解决方法.暴力法非常简单,但是它的速度不够快!那么我们该如何去做优化了?

一.算法题

题目

Given a string, find the length of the longest substring without repeating characters.

Example

  • Given "abcabcbb", the answer is "abc", which the length is 3.
  • Given "bbbbb", the answer is "b", with the length of 1.
  • Given "pwwkew", the answer is "wke", with the length of
  • Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

二.算法题解读

题目大意:给定一个字符串,找出不含有重复字符的最长子串的长度

解读Example

  • 给定"abcabcbb",没有重复字符的最长子串是"abc",那么长度就是3
  • 给定"bbbbb",最长子串就是"b",长度就是1
  • 给定pwwkew,最长子串就是"wke",长度为3,
  • 注意,必须是一个子串."pwke",是子序列,而不是子串

三."滑动窗口"优化解决

使用暴力法解决是非常简单,但是在暴力法中我们会反复检查一个子字符串是否含有重复的字符.但其实没有这个必要.

四.前导关键词介绍

  • HashSet

HashSetJava中实现Set接口.由哈希表支持.它不保证Set的迭代顺序,但是它利用Hash的原理来确保元素的唯一性.在HashSet中,元素都存到HashMap键值对的key上面.而Value时有一个统一的Hash值.

  • HashSet的插入

当有新的值加入时,底层的HashMap会判断Key值是否存在,如果不存在则插入新值.同时这个插入的细节会按照HashMap插入细节.如果存在则不插入.

  • 滑动窗口

滑动窗口:是指的是数组/字符串问题的常用抽象概念.窗口通常在数组/字符串中由开始和结束的索引定义的一系列元素的集合.即可[i,j)(左闭,右开).而滑动窗口是可以将2个边界向某一个方向"滑动"的窗口.例如,我们将[i,j)向右滑动1个元素,则它将变成[i+1,j+1)(左闭,右开);

四.思路

如果从索引i到j-1之间的子字符串S[ij]已经被检查为没有重复字符.那则只需要检查s[j]对应的字符是否存在于子字符串s[ij];

由于在C语言中是没有集合这一个概念的.所以我们使用java来实现.我们可以通过HashSet作为活动窗口.那我们只需要用O(1)的时间来完成对字符是否在当前子字符串的检查.

我们使用HashSet将字符存储在当前窗口[i,j),最初i=j .然后我们向右侧滑动索引j,如果它不在HashSet中,则我们会继续滑动j.直到s[j]已经存在于HashSet中,此时,我们就已经找到的没有重复字符的最长子串将会以索引i开头.如果我们将所有的i,都做如此操作即可得到结果.

五.实现

Java Code

六.复杂度分析

  • 时间复杂度:o(2n) = o(n);在最糟糕的情况下,每个字符顶多被i,j访问2次.
  • 空间复杂度:o(min(m,n)).窗口滑动法需要O(K)的空间,K指的是集合大小.而集合的大小取决于字符串n的大小以及字符串集的大小.

小编OS:

如有疑问,留言即可.胖C会利用空余时间给大家做一个简单解答的. 持续更新关注公众号!

本文分享自微信公众号 - HelloCode开发者学习平台(HellCode_CC),作者:CC老师

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

原始发表时间:2018-08-13

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 开篇词|用最本质的方法坚守

    做Hello Coder 开发者免费学习专栏,是早在3年前就已经很想做的事情.这也是坚持做知识付费的原动力.我相信"全力以赴是一种态度". 3年间也一直...

    CC老师
  • Python 基础部分--了解Python

    作为初学者,比起其他编程语言,Python是最容易上手的.Python追求的是找到最好的解决方案,而其他语言追求的是多种解决方案. Python在语言上非常解决...

    CC老师
  • iOS开发-音视频开发

    5G网络作为第5代的移动通信网络,它的网络峰值传播速度可1以达到10Gbps/s.这比4G的的传输速度快数百倍.举个例子,整部超高画质电影下载可在1秒钟之内下载...

    CC老师
  • Memcached 命令执行漏洞(CVE-2016-8704、CVE-2016-8705、CVE-2016-8706)简析

    Author: p0wd3r, dawu (知道创宇404安全实验室) Date: 2016-11-01 0x00 漏洞概述 1.漏洞简介 Memcached...

    Seebug漏洞平台
  • 开源在线编辑复合自动图表

    很多企业的业务对标准数据图表有很多的业务系统需求,而开发的节奏一直跟不上的。在报表开发中,很多的企业的流程是这样的: 1、BI负责数据的获取整合加工; 2、业务...

    用户3357544
  • 泛洪算法过程的终端

    摘要:泛洪是所有分布式网络算法中最简单和最基本的算法之一。节点通过向其所有相邻节点发送消息来开始该过程,在下一轮中将消息转发给他们未从其接收消息的所有相邻节点,...

    罗大琦
  • ZooKeeper构建分布式锁(选译)

    作者:Scott Leberknight 译者: java达人 来源:http://www.sleberknight.com/blog/sleberkn/en...

    java达人
  • python 上传下载 OSS 文件

    实现的功能很简单,先设置好云的 AccessKeyId 和 AccessKeySecret ,然后设置你所访问的 bucket 所在的区的链接和你所需要访问的 ...

    周小董
  • 【JavaScript小项目】在网页上显示选择的图片

    efonfighting
  • POJ2318 TOYS 判断点与直线位置关系 【计算几何】

    Calculate the number of toys that land in each bin of a partitioned toy box.

    ACM算法日常

扫码关注云+社区

领取腾讯云代金券