leetcode(3)——无重复字符的最长子串

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

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

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

// 判断给定的子串是否包含重复字符
function isUnique(str, start, end) {
  const chars = [];
  for(let i = start; i < end; i++) {
    const char = str[i];
    if(chars.indexOf(char) !== -1) { // 字符已存在，本字符串不符合条件
      return false;
    }
    chars.push(char); // 添加字符
  }
  return true;
}

// 获取字符串最长子串长度
function lengthOfLongestSubstring(s) {
  let max = 0;
  for(let i = 0; i < s.length; i++) {
    for(let j = i+1; j <= s.length; j++) {
      if(isUnique(s, i, j)) { // 判断子串是否唯一
        max = Math.max(max, j - i); // j - i 为当前子串长度
      }
    }
  }
  return max;
}

function lengthOfLongestSubstring(s) {
  const set = new Set();
  const max = 0;
  let i = 0;
  let j = 0;
  
  while(i < s.length && j < s.length) {
    if(!set.has(s[j])) { // j 不在set中，set中添加s[j],j后移，同时更新最大子串长度
      set.add(s[j]);
     	j++;
      max = Math.max(max, j - i);
    } else {
      set.delete(s[i]); // 移除set左边的数据，i后移一位
      i++;
    }
  }
  return max;
}

function lengthOfLongestSubstring(s) {
	const map = {}; // 保存 字符和下标的映射关系，如果字符重复，从map拿到位置，i直接跳到这个位置
  let max = 0;
  
  for(let i = 0, j = 0;j < s.length;j++) {
    const char = s[j];
    if(map[char] !== undefined) { // 当前字符存在重复，需要将i更新
      i = Math.max(i, map[char]); // 如果i的当前位置大于map[char]，不能更新为map[char]
    }
    max = Math.max(max, j - i + 1); // 由于j最大是s.length-1，所以最大子串长度需要+1
    map[char] = j + 1; // 保存映射关系
  }
  return max;
}