leetcode-3
https://leetcode.com/problems/longest-substring-without-repeating-characters/
1 | /** |
1th wr:
Input
“ “
Output
0
Expected
1
1 | /** |
2th wr:
Input
“dvdf”
Output
2
Expected
3
++j <= len 是为了substring(i, j)检查最末位字符。
这次错在i跳跃的太过了,改成i++ ac
不过耗时太长了:
Runtime: 264 ms, faster than 29.80% of JavaScript online submissions for Longest Substring Without Repeating Characters.
sample 92 ms submission1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function(s) {
var set = new Set() ; var l = 0 , r = 0 , max = 0 ;
while( l < s.length && r < s.length ){
if( !set.has(s[r])){
set.add(s[r++]);
max = Math.max( max , r - l );
}else{
set.delete(s[l++]);
}
}
return max;
};
sample 88 ms submission:
1 | /** |
同样用set,一定是我比较的方式不对,果然代码越多性能越好
改进我的答案:
1 | /** |
Runtime: 112 ms, faster than 58.54% of JavaScript online submissions for Longest Substring Without Repeating Characters.
还有直接搜索的答案:
sample 76 ms submission1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function(s) {
var maxLen,
l,
r;
if (s.length < 2) {
return s.length;
}
maxLen = 0;
for (l = 0, r = 1; r < s.length; r++) {
i = s.lastIndexOf(s[r], r-1);
if (i >= 0) {
maxLen = Math.max(maxLen, r - l);
l = Math.max(l, i + 1);
}
}
return Math.max(maxLen, r - l);
};