003.LongestSubstringWithoutRepeatingCharacters
首先考虑特殊情况,如:
- 空字符串
- 全部不重复
- 全部重复
如果用if
语句判断,则需要写一些代码,正好ES6
里提供了这样一种结构:Set
,Set
只存储不重复的值,利用它,可以很方便地判断字符串是否重复,所以:
const sub = new Set([...s])
const N = s.length
if (sub.size !== N) {
}
如果sub
存储的值的个数和字符串本身长度不一致,说明字符串包含重复字符,这时我们才另做处理,如果是全部重复或空字符串,直接返回sub.size
即可。
包含重复字符串的情况下,解决思路如下:
依次添加字符到Set
结构,如果再次遇到先前的字符,则保存当前最大长度,清空Set
,再次计算下一个不重复子串的长度,直到得到最长的子串长度。
不考虑特殊情况,所有情况统一对待。假设当前子串为空,依次遍历所给字符串中的字符,如果该字符没有在子串中,则添加到子串,如果已经在子串中,则和解法一类似,保存当前子串的最大长度,稍有区别的是,此时不应该清空子串,而是保留子串中当前字符所在位置之后的子串:
const j = sub.indexOf(s[i])
if (j === -1) {
sub += s[i]
} else {
if (sub.length > len) {
len = sub.length
}
sub = sub.substr(j + 1) + s[i]
}
例如abcabcbb
,一开始得到子串abc
,接着又遇到一个a
,因为它出现在前面的不重复子串中,所有应该去掉子串中的a
,得到bc
,加上s[i]
字符组成一个新的子串,通过不断比较子串的长度,得到最大值。
运行效率解法二比解法一高出许多,可能因为解法一中Set
的clear
、add
方法比较耗时?