最长无重复子串

1. 题目描述

给定一个数组arr，返回arr的最长无的重复子串的长度(无重复指的是所有数字都不相同)。

2. 思路

1. 思路一
   • 遍历的时候使用set统计是否存在，不存在则+1，存在则重新统计
2. 思路二
   • 滑动窗口：经典的滑动窗口是个队列，但是这里只要计算长度，所以end和start两个位置即可

3. 实现

3.1. set

func lengthOfLongestSubstring(s string) int {
    maxCount := 0
    for i := 0; i < len(s); i++ {
        visited := make(map[byte]bool, 0)
        count := 0
        for j := i; j < len(s); j++ {
            if visited[s[j]] {
                break
            }
            visited[s[j]] = true
            count++
            maxCount = max(maxCount, count)
        }

    }
    return maxCount
}


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

3.2. 滑动窗口

func lengthOfLongestSubstring(s string) int {
    if s == "" {
        return 0
    }

    start := 0
    end := 0
    res := 0
    m := make(map[byte]int, 0)
    for end < len(s) {
        index, ok := m[s[end]]
        // start-end之间有重复的字符，更新start的位置
        if ok {
            start =  max(start, index+1)//注意这里是max(start,index+1)而不是index+1。
            //比如abba的情况，如果是index+1，那么end到达最后一个a时,start更新为1，end为3，那么res就是3-1+1=3，显然是错误的
        }
        m[s[end]] = end
        res = max(res, end-start+1)
        end++
    }

    return res
}

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

4. 参考

• 找到字符串的最长无重复字符子串_牛客题霸_牛客网
• 画解算法：3. 无重复字符的最长子串 - 无重复字符的最长子串 - 力扣（LeetCode）
• 滑动窗口 - 无重复字符的最长子串 - 力扣（LeetCode）