【刷题第三天】无重复字符的最长字串
一、题目描述:
给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。
示例
示例 1:
输入: s = "abcabcbb"输出: 3 解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
示例 2:
输入: s = "bbbbb"输出: 1 解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
二、思路分析:
这肯定是个滑动窗口的题目,但是我没有发现这个窗口如何滑动,因此我就想了这样一种办法。
题目要求是无重复字符串,因此我决定设置一对象 alpha
记录每个字母第一次出现的位置,举个栗子:
str = 'abcac'
遍历前三个字符后,alpha 改变为 {a: 0, b:1, c:2}
接着往后遍历,发现 alpha['a'] = 0 ,说明前面已经出现过 a 字符,因此比较此时的无重复长度与最大长度的大小,然后截断 a 字符以前的字符(重新赋值为 undefined),即 alpha['a'] = undefined,然后重新赋值当前字母新位置,即 alpha['a'] = 3
继续往后遍历,发现 alpha['c'] = 2 ,说明前面仍然出现出重复 c ,依次运行上述流程,即 alpha['b'] = undefined,alpha['c'] = undefined。然后重新赋予当前字母位置。
思路好像看起来就挺复杂的,但是的确可以成功 OA
三、AC 代码:
四、总结:
通过最后的 AC 时间,我可以看到,当前使用的算法效率是非常低的,差点 Time Out 。我自己反思了一下,主要问题出在滑动上,这是明显的滑动窗口题目,但是我没有推出滑动的方式,反而通过模拟的方式来进行实现,因此造成耗时很久。
好慢的做法,明天的目标是不看题解思考出滑动窗口的运行方式,然后重做这个题目。
版权声明: 本文为 InfoQ 作者【白日梦】的原创文章。
原文链接:【http://xie.infoq.cn/article/2591ff853390519aab094c491】。文章转载请联系作者。
评论