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

题目链接：3. 无重复字符的最长子串
题目描述：

思路：典型的 双指针+hash，定义两个指针left，right，用于维护一个没有重复字符的区间，这个区间内的字符都是没有重复的，初始时候left和right都指向同一个位置，right指针会在遍历字符串时候一直++，在right++的过程中会将每个字符添加到hash结构中，left++的条件是当right++遇到了重复字符的时候，开始进行区间去重（更新left的位置，使得[left,right]没有重复字符），跑到下一个使得当前区间[left,right]没有重复字符的位置。并且在遇到重复字符时候，先计算答案，再去更新left指针。最后整体遍历完了在计算一遍答案即可。

代码：

func lengthOfLongestSubstring(s string) int {
	n := len(s)
	if n <= 1 {
		return n
	}
	maps := make(map[byte]struct{}, len(s))
	left, right := 0, 0
	ans := 0

	for ; left <= right && right < n; right++ {
		if _, ok := maps[s[right]]; ok { // 包含了则计算答案,然后移动左指针直到不包含
			ans = max(ans, right-left) //计算答案
			for ; left <= right; left++ { // 更新left指针和map，直到区间没有重复字符
				if _, ok := maps[s[right]]; ok {
					delete(maps, s[left])
				} else { // 当前位置还没添加map的，需要添加进去
                    maps[s[right]] = struct{}{}
					break
				}
			}
		} else {
			maps[s[right]] = struct{}{}
		}
	}
	ans = max(ans, right-left)
	return ans
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34