「No.03」【 每日壹题 】

• LeetCode算法题之-无重复字符的最长子串
  • 示例
  • 思路
  • 参考答案

LeetCode算法题之-无重复字符的最长子串

LeetCode算法题之-无重复字符的最长子串

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

示例

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

思路

j 0 0 0 1 2 3 4 5

{ a b c a b c b b}

i 0 1 2 3 4 5 6 7

s = "abcabcbb"

创建一个set集合，如果集合中不存在当前字符就添加，否则从集合中删除 定义俩指针i，j分别指向当前串，i为索引，j表示当前不存在连续的字符串时，从下个字符在开始判断。如果集合中存在是s[i]则删除s[j]，j++，在判断集合中是否存在s[i]，存在继续删除s[j]，最后没有就将s[i]添加到集合中，如果集合中没有s[i]，s[i]添加到集合中，比较字符串最大长度，Math.max(maxLength, set.size)

参考答案

详细信息

/**
 * @param {string} s
 * @return {number}
 */

var lengthOfLongestSubstring = function (s) {
  const set = new Set()
  let i = 0, j = 0, maxLength = 0
  if (s.length === 0) return 0
  for (i; i < s.length; i++) {
    if (set.has(s[i])) {
      set.delete(s[j])
      j++
      while (set.has(s[i])) {
        set.delete(s[j])
        j++
      }
      set.add(s[i])
    } else {
      set.add(s[i])
      maxLength = Math.max(maxLength, set.size)
    }
  }
  return maxLength
}