3. Longest Substring Without Repeating Characters

题目 #

Given a string s, find the length of the longest substring without repeating characters.

思路1 #

  • 暴力遍历，每个子字符串都判断是否没有重复字符串

思路2 #

  • 两个指针，i和j，j代表右侧，i代表左侧
  • j向后遍历，判断i和j之间是否有和j对应字符相同的
  • 如果有，计算长度，i移到相同的字符后面
  • 使用hashMap进行判断
 1func LengthOfLongestSubstring(s string) (result int) {
 2	hashMap := make(map[byte]int)
 3	for i, v := range s {
 4		i1, ok := hashMap[byte(v)]
 5		if !ok {
 6			hashMap[byte(v)] = i
 7			continue
 8		}
 9		if result < len(hashMap) {
10			result = len(hashMap)
11		}
12		hashMap[byte(v)] = i
13	}
14	if result < len(hashMap) {
15		result = len(hashMap)
16	}
17
18	return
19}

思路3 #

  • 在思路2的基础上，将hashMap换成数组，128位
  • 由于初始化为0，我们使用index+1来作为value
 1func LengthOfLongestSubstring(s string) (result int) {
 2	var charMap [128]int
 3	i := 0
 4	for j, v := range s {
 5		index := charMap[byte(v)]
 6		if index > i {
 7			// 0 1 2 3
 8			// a b c a
 9			// i     j
10			length := j - i
11			if result < length {
12				result = length
13			}
14			i = index
15		}
16		charMap[byte(v)] = j + 1
17	}
18	// 0 1 2 3
19	// a b c d
20	// i
21	length := len(s) - i
22	if result < length {
23		result = length
24	}
25
26	return
27}

思路4 #

  • 在思路3的基础上，最后一段怎么看都不爽
  • 在j移动过程中动态计算长度，不用在遍历完再来判断一遍
 1func LengthOfLongestSubstring(s string) (result int) {
 2	var charMap [128]int
 3	i := 0
 4	for j, v := range s {
 5		index := charMap[byte(v)]
 6		// 0 1 2 3 4
 7		// a b c b d
 8		// i     j
 9		// index = 2
10		if i < index {
11			i = index
12		}
13		length := j - i + 1
14		if result < length {
15			result = length
16		}
17		charMap[byte(v)] = j + 1
18	}
19
20	return
21}