算法Code-无重复字符的最长子串

微信公众号:glmapper工作室

如有问题或建议,请公众号留言

最近更新:

题目

给定一个字符串,找出不含有重复字符的 最长子串 的长度。

示例:

给定 "abcabcbb" ,没有重复字符的最长子串是 "abc" ,那么长度就是3。

给定 "bbbbb" ,最长的子串就是 "b" ,长度是1。

给定 "pwwkew" ,最长子串是 "wke" ,长度是3。请注意答案必须是一个子串,"pwke" 是 子序列 而不是子串。

方案1

思路:

字符对应的数字作为下标

初始化一个255的boolean作为所有可能出现的字符对应的存在可能性,不存在重复的均为false,存在重复的,则对应的下标置为true。

两个指针进行移动,前指针先不动,后指针移动并根据当前字符对应整数下标是否为false或者true进行判断。如果是false,则表示没有重复,则指针向后移动一位;如果为true,表示存在重复,则后指针停止移动,并计算当前字串长度,且将boolean数组重置,第一个指针向前移动一位,后指针指向当前前指针。

方案2

思路:

以一个hashmap作为辅助,map的key存储的是字符,value存储的是该字符当前的位置,首先设置一个头指针,指向字符串开头,那么从开始遍历字符串,如果map当中不包含这个字符,那么用这个字符当前所在的位置减去头指针的位置,然后与最大长度做比较,选打的成为最大长度,然后把当前字符的以及位置放入map,以abba为例,头指针指向a,当前为a,那么长度为1,map。put(‘a’,0),当前为b,那么长度为2,map.put('b',1),如果说map中存在当前字符,那么把头指针指向,头指针当前的位置与map中存储该字符位置的下一个位置当中的较大者,成为新的头指针位置,比如当走到第二个b的时候,那么头指针原来是0,当前map中存放b的位置是1,那么头指针指向2,所以长度为1,比最大长度小不进行替换,最后将当前的字符及位置放入map,现在是map.put('b',2),然后走到了a,那么当前map中a的位置是0,那么它的下一个位置是1,与当前头指针位置2相比,小于当前头指针的位置,那么头指针不跟新,所以长度为2,与最大长度相等,所以不替换,最后求出最大长度为2.

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180620A0BNCX00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券