[数据结构与算法]leetcode---js实现无重复字符的最长子串

题目描述

• 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
• 示例 1:
• 输入: s = “abcabcbb”
• 输出: 3
• 解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
• 示例 2:
• 输入: s = “bbbbb”
• 输出: 1
• 解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
• 示例 3:
• 输入: s = “pwwkew”
• 输出: 3
• 解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
• 请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。
• 示例 4:
• 输入: s = “”
• 输出: 0

解决方法

方法一：暴力解法+Set

• 解题思路
• 以每个字符串为开头遍历一遍，也就是总共遍历两遍。
• 知识点
• Set类似于数组，但是成员的值都是唯一的，没有重复的值。
• Set.prototype.add(value)：添加某个值，返回 Set 结构本身。
• Set.prototype.has(value)：返回一个布尔值，表示该值是否为Set的成员。
• Set.prototype.delete(value)：删除某个值，返回一个布尔值，表示删除是否成功。

    //暴力解法+Set
    var lengthOfLongestSubstring = function(s) {
        let count=0;
        for(let i=0;i<s.length;i++){
            let set=new Set();
            let max=0;
            let j=i;
            while(j<s.length&&!set.has(s[j])){
                set.add(s[j]);
                max++;
                j++;
            }
            count=Math.max(count,max);
        }
        return count;
    };

方法二：滑动窗口

• 解题思路
• 循环去掉左边第一个元素，直到窗口中元素无重复，此时再扩大窗口。主要就是进行扩张与收缩，右指针扩张到滑动窗口不满足条件的时候暂停，左指针开始收缩窗口，让窗口满足条件后右指针再进行扩张。

    var lengthOfLongestSubstring = function(s) {
        let count=0;
        let set=new Set();
        //左指针用来收缩窗口
        let left=0;
        //右指针用来扩张窗口
        let right=0;
        while(left<s.length){
        //如果不重复，就不断扩张窗口，元素添加到set中
            while(right<s.length&&!set.has(s[right])){
                set.add(s[right]);
                right++;
            }
            //元素重复了，先记录子串长度，然后收缩窗口
            count=Math.max(count,right-left);
            //收缩窗口
            set.delete(s[left]);
            left++;
        }
        return count;
    };