无重复字符的最长子串的长度

题目链接

解题思路

假设有个字符串"abcabca"
首先读懂题目,字符指的是个单个字母'a' 'b'这种， 子串指的是"ab" "abc" "abca"， "ac"不是子串，所以要求是连续的。无重复字符的意思就是指"abc"中没有一样的字符，而"abca"有两个'a'就重复了。
最直接的思路是使用滑动窗口，用窗口右边的指针记录窗口的位置，每次循环检测有重复的就移除左边的字符窜，添加右边的字符串，没有重复的就继续添加右边的字符串，这样循环字符串长度的次数，取出最长的结果

代码

func lengthOfLongestSubstring(s string) int {
 // 记录下标的hash表，也就是说的滑动窗口
 m := map[byte]int{}
 // 字符串的长度
 n := len(s)
 // 窗口的右指针和每次循环的结果
 rk, ans := -1, 0
 // 一共循环len(s)次，左指针的位置，初始值隐性地表示为 -1
 for i := 0; i < n; i++ {
  if i != 0 {
    // 左指针向右移动一格
    delete(m, s[i-1])
  }
  // m[s[rk+1]] == 0 判断这些字符是否出现过
  // go的整型数字默认值是0
  for rk+1 < n && m[s[rk+1]] == 0 {
    // 取ascii码做key
    m[s[rk+1]]++
    // 不断地移动右指针
    rk++
  }
  // 第 i 到 rk 个字符是一个极长的无重复字符子串
  // rk - i + 1算出来当前子串的长度
  // 从len(s)个结果中选出最长的
  ans = max(ans, rk-i+1)
 }
 return ans
}

func max(x, y int) int {
  if x < y {
    return y
  }
  return x
}

结果测试

func main() {
  var s1 = "bbbbb"
  var s2 = "abcabca"
  strLen1 := lengthOfLongestSubstring(s1)
  fmt.Println(strLen1) // 1
  strLen2 := lengthOfLongestSubstring(s2)
  fmt.Println(strLen2) // 3
}