3-无重复字符的最长子串.md

无重复字符的最长子串.md

原题

解法

思路: 这道题目主要用到的思想是: 滑动窗口

什么是滑动窗口？

其实滑动窗口我们可以看出一个队列，比如题目中 abcabcbb, 进入这个队列（窗口）为abc此时满足题目要求，当再进入一个a,也就是当窗口向右扩大的时候，队列变成了abca,这个时候不满足要求，所以，我们要移动这个队列。

具体应该如何移动呢？

我们只需要把队列的左边的元素移除出去就可以了,直到满足题目要求!

一直维持这样的队列，找出队列出现最长的长度时候，求出解。

具体实现: 在js中我们使用一个数组来维护滑动窗口

遍历字符串，判断字符串是否在滑动窗口数组里面

不在则push进数组 在则删除滑动窗口数组里相同字符以及相同字符前的字符，然后将当前字符push进数组 然后将max更新为当前最长子串的长度 遍历完成，返回max即可。

/**
 * 这个思路太清晰了
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
  // 滑动窗口初始化为一个空数组
  let arr = [];
  // 要返回的字符串的长度
  let max = 0;
  for (let i = 0; i < s.length; i++) {
    // 使用 indexOf 判断是否在数组中出现过
    let index = arr.indexOf(s[i])
    // � 如果出现过
    if (index !== -1) {
      // 从数组开头到当前字符串全部截取掉
      arr.splice(0, index + 1);
    }
    // 在窗口右边放进新的字符
    arr.push(s.charAt(i));
    // 更新下最大值
    max = Math.max(arr.length, max);
  }
  // 返回
  return max;
};

这里再使用一个标准版的滑动窗口的解法，和第76/438题的解法差不多

const lengthOfLongestSubstring = function (s) {
    let left = 0;
    let right = 0;
    let res = 0;
    let window = {};
    
    while (right < s.length) {
        let c1 = s[right];
        window[c1] ? window[c1]++ : window[c1] = 1;
        right++;
        
        // 当匹配到某个字符串有重复的时候，从left开始，一直匹配到left等于c1的初始位置，这样 c1 就只有一个了，也就没有重复了
        while (window[c1] > 1) {
            let c2 = s[left];
            window[c2]--;
            left++;
        }
        res = Math.max(res, right - left);
    }
    
    return res;
}

let s = [];
let result = lengthOfLongestSubstring(s);
console.log(result)

var lengthOfLongestSubstring = function(s) {
    // 哈希集合，记录每个字符是否出现过
    const occ = new Set();
    const n = s.length;
    // 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
    let rk = -1, ans = 0;
    for (let i = 0; i < n; ++i) {
        if (i != 0) {
            // 左指针向右移动一格，移除一个字符
            // 相当于每次都清空 occ 是吗？
            occ.delete(s.charAt(i - 1));
        }
        // for 每次循环的时候，都是使用的前一次计算后的 rk，为啥呀？
        // 
        while (rk + 1 < n && !occ.has(s.charAt(rk + 1))) {
            // 不断地移动右指针
            occ.add(s.charAt(rk + 1));
            ++rk;
        }
        // 第 i 到 rk 个字符是一个极长的无重复字符子串
        ans = Math.max(ans, rk - i + 1);
    }
    return ans;
};

function lengthOfLongestSubstring(s) {
    var map = new Map();
    var max = 0, i = 0, j = 0;
    while (j < s.length) {
        i = map.has(s[j]) ? Math.max(map.get(s[j]) + 1, i) : i;
        map.set(s[j], j++);
        max = Math.max(j - i, max);
    }
    return max;
};