https://leetcode.com/problems/longest-substring-without-repeating-characters/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    let i = 0;
    let j = 0;
    let ans = 0;
    const len = s.length;
    while(i < len && ++j < len) {
        let t = s.substring(i, j);
        if ([...new Set(t.split(''))].length === t.length) {
            ans = Math.max(ans, j - i);
        }
        else {
            i = j - 1;
        }
    }
    return ans;
};

1th wr：
Input
“ “
Output
0
Expected
1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    let i = 0;
    let j = 0;
    let ans = 0;
    const len = s.length;
    while(i < len && ++j <= len) {
        let t = s.substring(i, j);
        // console.log(i, j, t);
        if ([...new Set(t.split(''))].length === t.length) {
            ans = Math.max(ans, j - i);
        }
        else {
            i = j - 1;
        }
    }
    return ans;
};

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 submission

1
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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    var set = new Set();
    var res = 0;
    var l = 0;
    var r = 0;

    while(l<=r && r< s.length){
        // console.log("~~", l, r, set);
        if(!set.has(s[r])){
            set.add(s[r]); 
        }else{
            while(s[l]!=s[r]){
                set.delete(s[l]);
                l++;
            }
            l++;
        }
        r++;
        // console.log("res", l, r);
        res = Math.max(res, r-l);
    }
    return res;
};

同样用set，一定是我比较的方式不对，果然代码越多性能越好

改进我的答案：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    let l = 0;
    let r = 0;
    let ans = 0;
    let set = new Set();
    const len = s.length;
    while(l < len && r < len) {
        // console.log(l, r);
        if (!set.has(s[r])) {
            set.add(s[r++]);
            ans = Math.max(ans, r - l);
        }
        else {
            set.delete(s[l++])
        }
    }
    return ans;
};

Runtime: 112 ms, faster than 58.54% of JavaScript online submissions for Longest Substring Without Repeating Characters.

还有直接搜索的答案：
sample 76 ms submission

1
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);
};