【前端也得会算法】3. 无重复字符的最长子串 [ 中等 ]-一一网

Offer 驾到，掘友接招！我正在参与2022春招打卡活动，点击查看活动详情。

一、题目描述：

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

示例

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

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

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

复制代码

提示：

0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成

二、题解：

方法一数组截取法

原理。使用数组记录不重复字符，判断最长数组长度即可。
思路。
- 遍历字符串
- 如果记录的数组存在该字符串，先记录最长数组长度。再截取掉出现该字符串之前的数组元素
- 继续将不重复的字符串放入数组中

代码：

var lengthOfLongestSubstring = function(s) {
    let arr = []
    let max = 0
    for(let i of s){
        if(arr.includes(i)){
            max = Math.max(max, arr.length)
            arr.splice(0, arr.findIndex(it => it === i)+1)
        }
        arr.push(i)
    }
    return Math.max(max, arr.length)
};
复制代码

方法二 Map位置记录法

原理。使用Map记录字符位置以及记录字符开始位置来计算最大长度。
思路。
- 遍历字符串
- 如果存在map里面已有的字符串
- 改变start位置，根据map.get(s[i])和start大小来决定
- 设置或重置s[i]为当前下一个值的位置
- 比较获得最大值

代码：

var lengthOfLongestSubstring = function(s) {
    let map = new Map()
    let max = 0
    let start = 0
    let n = s.length
    for(let i = 0; i < n; i++){
        if(map.has(s[i])){
            start = Math.max(map.get(s[i]), start)
        }
        map.set(s[i], i + 1)
        max = Math.max(max, i + 1 - start)
    }
    return max
};
复制代码