3. 无重复字符的最长子串 JS双指针滑动窗口解法_js双指针计算无重复字符的最长子串图解

⚡️3. 无重复字符的最长子串⚡️

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

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

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

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

示例 4:
输入: s = “”
输出: 0

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

⚡️分析⚡️

找最大的不重复子串长度，可以用双指针维护滑动窗口的思想，左指针不动，右指针往右遍历，如果遇到重复的字符，那么左指针就要移到这个重复字符的后一位，比如"abcdaghia"，右指针遇到第二个a，左指针就移到b，当右指针遇到第三个a，左指针就移到g。
而对于如何判断某个字符是否重复，我的思路是，在遇到不重复字符时，将该字符及其下标变成键值对放入字典，然后右指针每次往右遍历，都调用一次字典的.get()方法判断有没有重复。

我第一次提交错误的地方是在if的判断条件那里出了错，判断重复字符时，不仅要有第一个"已含有这个字符"的条件，而且这个已含有字符的下标位置应该在滑动窗口内，也就是大于left。
举个例子：对于"abbcdaef"，因为b重复了，所以左指针在第二个b上，右指针继续往右遍历，当遍历到第二个a时，判断到字典中已有a，但这个a的下标在左指针的左边，即滑动窗口外面(相当于前面那部分子串因重复而废弃没用了)，所以不算是重复

代码如下：

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    let left = 0;
    let long = 0;
    const map = new Map();
    for(let right=0;right<s.length;right++){
        if(map.has(s[right]) && map.get(s[right]) >= left){
            left = map.get(s[right]) + 1;
        }
        long = Math.max(long,right-left+1);
        map.set(s[right],right);
    }

    return long;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

算法效率如图：





觉得该篇文章有用的请不要忘记忘记点击右下角的大拇指~

欢迎大家关注我的公众号：Smooth前端成长记录
公众号同步更新CSDN博客内容，想方便阅读博客的C友可以来关注我的公众号以便获得更优良的阅读体验~