算法练习12：无重复字符的最长子串(leetcode 3)

解题思路

初始：abcdfde

• 当没有重复值时，滑动窗口一直累加：
  第一个滑动窗口：abcdf，窗口长度5
• 当有重复值“d”时
  因为abcdf已经确认过为无重复序列了，所以这一段是不需要重新比较的，只需要更新重复字符中前一个d的下一个字符串f为新窗口的初始值
  第二个滑动窗口：fde，窗口长度3
• 取最大窗口长度：5

实现过程：

1. 创建一个哈希表，用来保存当前滑动窗口里的字符串，滑动窗口里的集合代表着不存在重复的子序列，指针start代表滑动窗口初始下标,初始为0
2. 遍历str，当前遍历下标为i，如果遍历的当前字符不在哈希表中，则将当前的字符保存到哈希表，且滑动窗口长度=i - start + 1；如果长度比历史长度大，则更新此值为最大值；比如“abcbde”，当滑动到"c"时，winLen = 3
3. 如果当前字符存在哈希表中，查看其在哈希表中记录的位置，start指针开始的移动，直至当前字符存在的位置的下一位，在这过程中哈希表将这些值都删掉，当移动到“b”时，发现b在哈希表有值，且对应下标是1，start移动到它的下一位2的位置，然后删除"ab"在哈希表的值，哈希表更新为"cb"
4. 然后继续遍历str，重复1,2,3过程，直至结束，就能得出最大不重复子序列了。

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
  
  let len = s.length;
  // 边界值，如果小于1个值，那么最长子串为它的长度
  if(len <= 1) {
    return len;
  }
  // 创建一个哈希表，保存当前滑动窗口的集合
  let map = new Map()
  // 记录最大长度
  let maxLen = 0;
  // 滑动窗口的初始位置
  let start = 0;
  // 当前滑动窗口的长度
  let winLen = 0;
  // 遍历字符串
  for(let i = 0; i < len; i++) {
      // 如果当前字符不存在哈希表，则将字符和其下标保存到哈希表中
      if(!map.has(s[i])) {
          // 更新滑动窗口长度
          winLen = i - start + 1
          // 如果滑动窗口大于最大长度，则更新最大长度
          if(winLen > maxLen) {
            maxLen = winLen
          }
      // 如果当前字符存在哈希表中，代表着有重复值，要更新哈希表
      }else {
          // start要移动到的位置，为之前这个字符的下标+1
          let newStart = map.get(s[i]) + 1
          // 滑动start到新位置，并将其中的字符在哈希表中删除
          while(start != newStart) {
            map.delete(s[start])
            start++;
          }
      }
      // 将当前遍历的值和其下标，更新到哈希表中
      map.set(s[i], i)

  }
  return maxLen
};

let str1 = "abcdfde"
let str2 = "abcabcbb"
let res = lengthOfLongestSubstring(str1)
console.log(res) // 5