3. 无重复字符的最长子串

40次阅读

共计 1132 个字符，预计需要花费 3 分钟才能阅读完成。

题目：给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。
示例 1:
输入: “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
示例 2:
输入: “bbbbb” 输出: 1 解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
示例 3:
输入: “pwwkew” 输出: 3 解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是子串的长度，”pwke” 是一个子序列，不是子串。

解答：1. 暴力破解
var lengthOfLongestSubstring = function(s) {
var l = s.length;
var re = 0;
for (var i= 0; i < l; i++) {//1
for(var j = i + 1; j <= l; j++){//2
if(check(i, j)) {
re = Math.max(re, j – i)
} else {
break
}
}
}
function check(start, end) {
var a = [];
for (var k = start; k < end; k++) {//3
if (a.indexOf(s[k]) !== -1) {
return false
} else {
a.push(s[k])
}
}
return true;
}
return re
};
上来就是一顿 for 循环操作，这样暴力写我们的 leetcode 肯定是不会给过的，因为遇到超级长的字符串测试用例，执行时间会超出时间限制，上面代码的优化空间很大。理一下逻辑，我们每次在 2 里面检测出有重复的字符时，记录这个重复字符前一次出现的位置 index，然后中断这次循环，开始下一次 1 的循环，并且 i 的位置应该为 index+1。比如在 i = 0 的时，在 2 循环里 j = 4 时就会出现重复的字符 d，字符 d 前一次出现的位置是 1，这时最长字符串长度是 4，并且被记录，这时应该开始 1 循环的下一次循环，并且是从 i = 2 开始。3 循环和 2 循环其实是不必要的，我们创建一个动态的字符串，把每次循环到的字符加进去并实时记录它的长度，遇到重复的字符串就砍掉字符第一次出现跟它之前的字符串，比如上图，i 循环到 4 时，出现重复字符 d,d 在之前出现的位置是 1，我们应该砍掉动态字符串位置 1 跟它之前的字符串，来保证它是无重复的字符串。代码如下
var lengthOfLongestSubstring = function(s) {
var l = s.length;
var re = 0;
var a = ”, index;
for (var i = 0; i < l; i++) {
index = a.indexOf(s[i])
if (index !== -1) {
a = a.slice(index + 1)
}
a+=s[i]
re = Math.max(re, a.length);