leetcode 03 无重复字符的最长子串

2020-06-28

滑动窗口（Sliding Window）算法

算法题

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

示例 1:

1
2
3

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

解题思路：我们可以通过一个数组来记录无重复子串，比较 s 中下一个字符是否在数组中存在，如果存在就删除，否则把下一个字符存进数组，比较数组的长度就可获得最大无重复子串的长度

 arr[0];先把第一个字符存进数组，这个数组存储的是无重复子串
 for (let i = 0; i < s.length; i++) {
      let j = i + 1;
      
      if( arr 有下标为 j 的字符 ){
      	删除下标为 i 和 i 之前的元素
}

[j]; 把第 j 个字符存入数组arr

比较[i]的最大长度 max
  }
  return max

滑动窗口算法

滑动窗口经常作为一个抽象的概念来处理数组/字符串问题,它可以将嵌套的循环问题，转换为单循环问题，降低时间复杂度, 窗口代表着一组数据/字符串元素，通过开头和结尾的索引来定义窗口。例如下图中滑动窗口就是长度固定为 2 的窗口。

上面这道题也是利用了滑动窗口算法，窗口由不重复的字符组成，题目求的就是窗口的最大长度。

如何维护滑动弄窗口呢？如何找出重复的字符？下面有两种方法

借助数组方法 indexOf(string i),当一个数组内存在 i 时，就会返回这个数组的下标，否则返回-1
借助哈希表的 has（string i）方法，当哈希表存在 i 为真，否则为假。

首先介绍通过数组来维护滑动窗口

新建一个用来存储不重复元素的数组 arr，数组的长度就是活动窗口的长度
i = 0 ，开启滑动窗口，添加数组元素，就相当于右移滑动窗口
当遇见重复字符的时候，删除 arr 数组中重复字符，将当前字符加入 arr 数组，
比较当前数组的长度和上一次的 max 值并取最大
依次滑动，直至移动 s 的最后一个字符

let lengthOfLongestSubstring = function(s) {
    let arr = [],
        max = 0;
    for (let i = 0; i < s.length; i++) {
        let index = arr.indexOf(s[i])
        if (index !== -1) {//重复了
          
            // 因为splice删除第二个参数是删除的个数，因此index要+1
            arr.splice(0, index + 1);//删除重复元素及其之前的元素
        }
        arr.push(s[i]);
        max = Math.max(arr.length, max); //每次都来更新max值
    }
    return max;
}

通过哈希表维护滑动窗口

新建一个哈希 occ
滑动窗口的区间长度是 [ i, rk] , rk 的初试值初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
检查是否有重复元素 rk + 1 < n && !occ.has(s.charAt(rk + 1)),把不重复元素加入哈希表
遇到重复元素时，由于 set 里面存储的元素顺序会发生变化，因此无法通过下标找到重复元素，因此可以删除 s 字符串的元素，occ.delete(s.charAt(i - 1));，直至删除重复元素。
滑动窗口的长度是 rk - i + 1 ，每次循环比较当前滑动窗口长度和 max 取最大。

// 哈希表 窗口区间就是[ i, rk]
var lengthOfLongestSubstring = function(s) {
    const occ = new Set();
    const n = s.length;
    
    let rk = -1,//  右指针
        max = 0; 
    for (let i = 0; i < n; i++) {
        if (i != 0) {//遇到了重复的字符            
            // 左指针向右移动一格，移除一个字符 这里结合下面的判断 直至删除重复字符
            occ.delete(s.charAt(i - 1));   
        }
        
        while (rk + 1 < n && !occ.has(s.charAt(rk + 1))) 
            occ.add(s.charAt(rk + 1)); //不重复的元素加入哈希表
            ++rk;  // 不断地移动右指针
        }

        // 第 i 到 rk 个字符是一个极长的无重复字符子串
        max = Math.max(max, rk - i + 1);
    }
    return max;
};

上面是通过 set 对象来维护滑动窗口，由于 set 只会存储 key 值，无法直接找到被删除元素。但是 map 存储的是键值对，key 是我们查找的字符，value 是 key 的位置。

var lengthOfLongestSubstring = function(s) {
    let map = new Map(),max = 0
    
    for (let i = 0, j = 0; j < s.length; j++) {
        if (map.has(s[j])) {
            // i 是重复元素的的下一个元素的下标 这里也就是滑动窗口的左侧移动到重复元素的下一个元素
            i = Math.max(map.get(s[j]) + 1, i)
        }
        max = Math.max(max, j - i + 1)
        map.set(s[j], j)
    }
    return max
};