LeetCode 3 无重复字符的最长子串

题目：

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

解题：

循环查找不重复的字符串

代码：

func lengthOfLongestSubstring(s string) int {
  l := 0
  ll := len(s)
  for i := 0; i < ll; i++ {
    ss := s[i:]
    m := make(map[int32]int32)
    for _, vv := range ss {
      if _, ok := m[vv]; ok {
        break
      } else {
        m[vv] = vv
      }
    }
    if len(m) > l {
      l = len(m)
    }
  }
  return l
}

时间复杂度O(n^2)，大力出奇迹，只能算是解出来了

看看官方给出的解法

func lengthOfLongestSubstring(s string) int {
  m := map[byte]int{}
  n := len(s)
  rk, ans := 0, 0
  for i := 0; i < n; i++ {
    if i > 0 {
      delete(m, s[i-1])
    }
    for rk < n && m[s[rk]] == 0 {
      m[s[rk]]++
      rk++
    }
    ans = max(ans, rk-i)
  }
  return ans
}


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

说是用了滑动窗口的方法，大致明白了是怎么一回事。

然而官方给出的方法只有击败了38.90%的用户，看来官方的水平也有很大的提升空间，要是能把效率最高的代码放出来就好了。