题目

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
示例 2:

输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
示例 3:

输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，”pwke” 是一个子序列，不是子串。
示例 4:

输入: s = “”
输出: 0

题解思路

方法一

使用队列去解题，字符串挨个进队列，遇到重复的就出列一个，继续遍历，依次判断，这个方法有个弊端，他返回的字符串个数是对的，但是返回的字符串是不对的。

方法二

滑窗的解题思路，遍历整个字符串，如果子串中与当前值没有重复元素，加入到变量 str 中，改变长度；如果有重复的，从重复位置向后滑动一位

代码实现

方法一：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    var res = 0, i = 0;
    var temp = [];
    while(i < s.length) {
        if(temp.indexOf(s[i]) === -1) {
            temp.push(s[i]);
        } else {
            temp.shift();
            continue;
        }
        res = Math.max(res, temp.length);
        i++;
    }
    return res;
};

方法二：

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) {
    // 初始长度为0
    let len = 0;
    // 记录无重复子串
    let str = '';
    // 遍历整个字符串，如果子串中与当前值没有重复元素，加入到 str 中，改变长度；如果有重复的，从重复位置向后滑动一位
    for(let i = 0; i < s.length; i++) {
        let char = s[i];
        let index = str.indexOf(char);
        if(index === -1) {
            str += char;
            len = len < str.length ? str.length : len;
        } else {
            str = str.substr(index+1) + char;
        }
    }
    return len;
};