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

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

题目信息

题目地址： 无重复字符的最长子串

题目内容：

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

示例 1:
  输入: s = "abcabcbb"
  输出: 3 
  解释: 因为无重复字符的最长子串是"abc"，所以其长度为3。
  
示例 2:
  输入: s = "bbbbb"
  输出: 1
  解释: 因为无重复字符的最长子串是"b"，所以其长度为1。
  
示例 3:
  输入: s = "pwwkew"
  输出: 3
  解释: 因为无重复字符的最长子串是"wke"，所以其长度为 3。
  
请注意，你的答案必须是子串的长度，"pwke" 是一个子序列，不是子串。
 
提示：
  0 <= s.length <= 5 * 104
  s 由英文字母、数字、符号和空格组成

题解

解法一

思路：

通过双重for循环来解决，创建一个数组存放不重复的字符串长度

第一层for循环来获取当前遍历的字符的索引，然后从原字符串中截取当前索引到原字符串末尾的字符串

第二层for遍历第一层截取到的字符串，并设置一个Set来存放不重复的字串长度，如果Set中含有当前遍历到字符串，就直接返回Set的size，否则就将当前字符串添加到Set中

最后返回存放不重复的字符串长度中最大的数字即可

代码实现：

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    if(s.length <= 1) return s.length
    const allStrLength = []
    const next = str => {
        const set = new Set()
        for(let i = 0; i < str.length; i++) {
            const curStr = str[i]
            if(set.has(curStr)) {
                return set.size;
            }
            set.add(curStr)
        }
        return set.size
    }
    for(let i = 0; i < s.length; i++) {
        allStrLength.push(next(s.slice(i)))
    }
    return Math.max(...allStrLength)
};

解法二

思路：

设置一个数组res来存放遍历过程中的不重复字符串，设置最大不重复长度max，使用for循环遍历字符串

遍历过程中，设置当前遍历字符串为curStr，判断curStr是否在res中，

如果在，就从res中截取从curStr的下一位到res结尾的数组，然后赋值给res

然后将curStr放到数组末尾，然后更新max的值，取max和res.length中最大的

最后返回max即可

代码实现：

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    if(s.length <= 1) return s.length
    let res = []
    let max = 0
    for(let i = 0; i < s.length; i++) {
        const curStr = s[i]
        const curStrIdx = res.indexOf(curStr)
        if(!!~curStrIdx) {
            res = res.slice(curStrIdx + 1)
        }
        res.push(curStr)
        max = Math.max(max, res.length)
    }
    return max
};

还可以使用队列思想

代码如下：

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    if(s.length <= 1) return s.length
    const res = []
    let max = 0
    for(let i = 0; i < s.length; i++) {
        const curStr = s[i]
        while(res.includes(curStr)) {
            res.shift()
        }
        res.push(curStr)
        max = Math.max(max, res.length)
    }
    return max
};