3. Loongest Substring Without Re

题目

给定一个字符串 s，找出这个不重复字符串的最长字串长度。

解析

找出这个字符串不重复子串的最大长度。
记录上一个不重复子串长度为 last_count 为 0
记录当前不重复子串长度 count 为 0，记 开头指针为 head，当我们使用指针 i 从前往后遍历，遇到没有出现的，就 count++；遇到出现过的，他的位置为 last，如果 last >= head ，说明在当前子串内发生重复了，有了相同字符了。这个时候

1. 对比 count 和 last_count 更新最长值
2. 下一次可能的最大长度是出现的 head 应该是 head = last+1
3. 当前最大长度应该是 i - head + 1

伪码

count = 0
head = 0
map[c]int
for i,idx in s
  if map[i] == nil
    map[i] = idx
    continue
  if map[i] != nil && map[i] >= head
    c := idx-head
     if c > count
         count = c
    head = map[i] + 1
    map[i] = idx

if len(s) - 1 - head + 1 > count
  count=len(s)-1-head+1
return count

提交代码

func lengthOfLongestSubstring(s string) int {
    m := make(map[uint8]int)
    count:=0
    head:=0
    i:=0
    
    for ;i<len(s);i++ {
        c := s[i] - 'a'
        num,ok := m[c]; 
        if !ok {
            m[c] = i
            continue
        }
        if num >= head {
            t := i - head
            if t > count {
                count = t
            }
            head = num + 1
        }
        m[c] = i
    }
    if i - head > count {
        count = i-head
    }
    return count
}

回顾

1. 本来打算用 [26]int 代替 map[uint8]int，结果字符有很多奇怪的东西
2. golang 字符串 s 用 range 遍历出的类型是 int32，用 s[i] 得到的类型是 uint8
3. golang 数组初始化整数为 0，字符串为 ""
4. 本题中计算两个索引之间的长度是 cur - head。没有 + 1。因为 cur 和 head 是不重复的