题目

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

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

暴力解法

这个题最容易想到的还是暴力解法，既然要找最大的子串， 我就从头开始一个一个找。

固定子串的左边界，右边界往右移动，逐个往子串中添加字符，直到子串中已经存在字符，这时找到一个最大子串不重复的子串 记录长度；左边界右移一个字符，继续操作，不断替换最大值。

这里的时间复杂度是 O(n2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// LenOfNonRepeatedSubstr 无重复子串的最大长度 1. 暴力之美
func LenOfNonRepeatedSubstr(str string) int {
	maxStr := ""
	cur := 0
	maxLen := 0
	for index := 0; index < len(str); index += 1 {
		if strings.Index(maxStr, string(str[index])) != -1 { // 找到了， 回退并且置空
			maxStr = ""
			index = cur     // 继续查找下一个位置开始的子串
			cur = index + 1 // 记录当前子串的起始位置
		} else { // 无重复 直接增加
			maxStr += string(str[index])
			if maxLen < len(maxStr) {
				maxLen = len(maxStr)
			}
		}
	}
	return maxLen
}

####

回溯的位置待查找

暴力解法在于，每次都重新开始匹配下一个位置，没有利用上次匹配到的位置，假如abcac 匹配到第二个a的时候，要重新从b开始匹配。

实际并不需要，abc是无重复的，后面的a已经重复了，我们只需要在abc中找到 a 重复的位置，把他之前的子串去掉，继续往后匹配.

比如abc 匹配到 a的时候 重复了，bca不重复继续往后匹配。时间复杂度 O(N)

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
// LenOfNonRepeatedSubstrV1 无重复子串的最大长度 利用已经比较的最大子串
func LenOfNonRepeatedSubstrV1(str string) int {
	maxStr := ""
	maxLen := 0
	for index := 0; index < len(str); index += 1 {
		for strings.Index(maxStr, string(str[index])) != -1 { // 找到了，去掉最左边的字符，继续查找
			// i..j 如果是最大不重复的，那么i+1...j 不可能是最大的
			// 直接将左边的去掉 看j+1是否在子串 逐个去掉左边的字符
			maxStr = maxStr[1:] // 去掉最左边的字符
			continue
		}
    // 以上for循环可等价于
    // pos := strings.Index(maxStr, string(str[index]))
		// if pos != -1 {
		// 	maxStr = maxStr[pos+1:]
		// }
    
		// j+1不在子串了
		maxStr += string(str[index])
		if maxLen < len(maxStr) {
			maxLen = len(maxStr)
		}
	}
	return maxLen
}

这个在匹配的时候 还是会遍历查找maxStr 中是否包含字符，这里做个改进

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// LenOfNonRepeatedSubstrV2 无重复子串的最大长度 利用已经比较的最大子串
func LenOfNonRepeatedSubstrV2(str string) int {
	maxLen := 0
	strMap := make(map[byte]struct{})
	rk := -1 // 初始化 rk 为左边的
	for index := 0; index < len(str); index += 1 {
		if index != 0 {
			delete(strMap, str[index-1]) // 存在重复的 就去掉左边
		}

		for rk+1 < len(str) {
			if _, ok := strMap[str[rk+1]]; !ok { // 不重复就放入 并且指针后移
				strMap[str[rk+1]] = struct{}{}
				rk += 1
			} else {
				break
			}
		}
		maxLen = max(maxLen, rk-index+1)
	}
	return maxLen
}

这里只是把字符串换成了 map，查找的时候不用遍历.

后来看别人总结，才发现 这个方法叫做 滑动窗口，维护一个窗口，上面的代码实现 就是 maxStr 或者strMap 窗口中出现过的字符，就逐步缩小左边窗口，之后继续扩大右边窗口。

不管叫什么字符串匹配 优化方法 都是从已经匹配的子串中，继续往后操作，就是利用前面的匹配，不能每次都重新开始。

一晚上一个算法， 真是衰🐶。