leecode刷题【滑动窗口】【js实现】

思路：滑动窗口+双指针

思路
移动和缩放滑动窗口[start,end]，始终保持区间内不重复。怎么移动呢，方法如下：
1.end从头向尾逐个遍历，扩大窗口；

start的位置要保证区间无重复，那就必须跳过区间内有重复的值。所以就需要用哈希表map记录每个字符最后一次出现的位置+1，如果这个位置更大说明这个字符又重复了，需要调整start位置到这里。如果位置比start位置更小，保持start不懂。因为start前是有重复元素的。

算法

定义不重复子串的开始位置为start，结束位置为end。[start,end]区间表示无重复的子串，即滑动窗口。求这个窗口的的最大长度。
2/ 定义map的结构(k,v)记录[start,end]中不重复子串的位置，其中key值为字符，value值为字符位置+1
随着end不断遍历向后，会遇到与[start, end]区间内字符相同的情况，此时将字符作为key值，获取其value值，并更新start，保证[start,end]区间内不存在重复字符

代码：

function maxLen(s) {
  let start = 0;
  let res = 0;
  let map = new Map();
  for (let end = 0; end < s.length; end++) {
    // 重复,更新start位置。
    if (map.has(s[end])) {
      //若map中重复元素的位置在滑动窗口前，则不更新位置
      start = Math.max(start, map.get(s[end]) + 1);
    }
    map.set(s[end], end);
    res = Math.max(end - start + 1, res);
  }

  console.log(res);
  return res;
}

最后一次出现的位置+1，如果这个位置更大说明这个字符又重复了，需要调整start位置到这里。

算法

定义不重复子串的开始位置为start，结束位置为end。[start,end]区间表示无重复的子串，即滑动窗口。求这个窗口的的最大长度。
定义map的结构(k,v)记录[start,end]中不重复子串的位置，其中key值为字符，value值为字符位置+1
随着end不断遍历向后，会遇到与[start, end]区间内字符相同的情况，此时将字符作为key值，获取其value值，并更新start，保证[start,end]区间内不存在重复字符

参考：https://leetcode.cn/problems/longest-substring-without-repeating-characters/solution/suan-fa-dong-hua-by-linsen80586-xvlf/

另一种写法
注意：需要先判断重复，再加入元素

var lengthOfLongestSubstring = function(s) {
  let res=0
  let str=''//滑动窗口
  for(let i=0;i<s.length;i++){
      let index = str.indexOf(s[i])
      //元素与滑动窗口重复，剔除重复元素及以前的元素
      if(index>-1){
          str = str.substr(index+1)
      }
        str +=s[i]
        res = Math.max(res,str.length)
  }
  return res
};

最后编辑于：2023.03.04 15:01:47

leecode刷题 【滑动窗口】【js实现】

leecode刷题【滑动窗口】【js实现】