博客

解法一：滑动窗口法



解题思路


1、用双指针维护一个滑动窗口，用来剪切子串。

2、不断移动右指针，直到遇到重复字符的时候把左指针移到前面的重复字符的下一位。（相当于把前面的重复字符删除）

3、移动指针过程中，记录窗口长度的最大值即为答案。

function lengthOfLongestSubstring(s){
    let l=0;
    let res=0;
    let map=new Map();
    for(let r=0;r<s.length;r++){
        if(map.has(s[r])&&map.get(s[r])>=l){
            l=map.get(s[r])+1;
        }
        //console.log(s.slice(l,r+1))
        res=Math.max(res,r-l+1);
        map.set(s[r],r);
        //console.log("map",map)
    }
    return res;
}

console.log(lengthOfLongestSubstring("abbcdea"))

在判断是否是重复字符的时候，别忘了加上 满足重复字符的索引大于左指针（&& map.get(s[r]) >= l） 这个附加条件，不然某些样例就会出错。比如 abbcdea这个 case，在遍历到最后一个字符 a 的时候，如果没有加上这个条件，最后一个 a 也会被认为是重复字符(与前面那个a重复，其实滑动窗口已经划过，与前面那个a没关系了)，从而产生错误。

正确代码，每个不重复子串如下：

错误代码：不写这个条件

&& map.get(s[r]) >= l）

的不重复子串如下：

解法二：遍历法


思路：代码的思路比较简单，就是维护一个数组arr，对原字符串遍历，判断字符是否在arr里面，不在的话就直接push进去，再重新判断max的大小；在的话就将之前重复arr字符之前的项全部去除，再重新push进去。

function lengthOfLongestSubstring(s) {
    let arr = [];
    let max = 0;
    for(let item of s){
        if(arr.includes(item)){
            let index = arr.indexOf(item);
            arr.splice(0, index + 1);
        }
        arr.push(item);
        max = max > arr.length ? max : arr.length;
    }
    return max;
};

知识点：



1. Array对象中的splice()方法


删除——可以删除任意数量的项，只需要指定2个参数：要删除的第一项的位置和要删除项的项数。

例如，splice(0,2)会删除数组中的前两项，从0开始，删两项。

插入——可以向指定位置插入任意数量的项，只需要提供3个参数：起始位置、0（要删除的项数）和要插入的项。

如果要插入多个项，可以再传入第四、第五，一直任意多个项。

例如，splice(2,1,”red”,”green”)会删除当前数组位置2的项，然后再从位置2开始插入字符串“red”和”green”。

替换——可以指向指定位置插入任意数量的项，且同时删除任意数量的项，只需要指定3个指定参数：起始位置、要删除的项数和要插入的任意数量项。

插入的项数不必与删除的项数相等。例如，splice(2,2,”red”,”green”)会删除当前数组位置2的项，然后再从位置2开始插入字符串“red”和“green”。

splice()方法始终都会返回一个数组，返回被删除的项目（如果没有删除任何项，则返回一个空数组）。会改变原数组。