Pengjielee's blog

题目

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

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

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

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

示例 4:
输入: s = ""
输出: 0

提示：

0 <= s.length <= 5 * 10^4
s 由英文字母、数字、符号和空格组成

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

JS实现

参考代码1：

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {
  // hashmap，记录每个字符是否出现过
  const map = new Map();
  // 无重复字符最长子串的左边界
  let left = 0;
  // 无重复字符最长子串的长度
  let max = 0;

  // 遍历字符串
  for (let i = 0; i < s.length; i++) {
    const ch = s[i];
    // 如果该字符已经出现过
    if (map.has(ch)) {
      // 更新左边界
      left = Math.max(left, map.get(ch) + 1);
    }
    // 设置hashmap，key存储该字符，value存储其下标
    map.set(ch, i);
    // 计算最大长度
    max = Math.max(max, i - left + 1);
  }
  return max;
};

参考代码2：

var lengthOfLongestSubstring = function (s) {
  // 充当hashmap的作用
  let result = "";
  // 无重复字符最长子串的长度
  let size = 0;

  // 遍历字符串
  for (let i = 0; i < s.length; i++) {
    const char = s.charAt(i);

    // 获取result中当前字符的下标
    const index = result.indexOf(char);
    // 如果result没有该字符，则拼接，并且更新size的长度
    if (index === -1) {
      result += char;
      size = size < result.length ? result.length : size;
    } else {
      // 如果有该字符，则从其下标+1的位置截取，再拼接当前字符
      result = result.substring(index + 1) + char;
    }
  }
  return size;
};

Go实现

package main

import (
  "fmt"
)

func main() {
  fmt.Println(lengthOfNonRepeatingSubStr("abcabcbb"))
  fmt.Println(lengthOfNonRepeatingSubStr("bbbbb"))
  fmt.Println(lengthOfNonRepeatingSubStr("pwwkew"))
}

func lengthOfNonRepeatingSubStr(s string) int {
  //字典，用于保存每个字符的最近下标（index）
  mapper := make(map[byte]int)
  //用于保存当前子串的开始下标（index）
  start := 0
  //用于返回，存储当前最长子串的长度
  maxLength := 0

  //遍历字符
  for i, ch := range []byte(s) {
    //如果该字符出现过，并且该字符的索引 比start大，更新start，小于start，什么也不做
    lastIndex, ok := mapper[ch];
    if ok && lastIndex >= start {
      start = lastIndex + 1
    }
    // if i-start+1 > maxLength {
    //   maxLength = i - start + 1
    // }
    maxLength = max(maxLength, i-start+1)
    mapper[ch] = i
  }
  return maxLength
}

func max(a int, b int) int {
  if a > b {
    return a
  }
  return b
}