给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
解法一：
使用二分法配合滑动窗口法
$O(n)$$O(nlogn)$func judge(s string, length int) bool {
//flag记录重复的字符数量
flag := 0
m := make(map[byte]int)
//构造map，key代表字符，value代表在lenght的窗口长度下，key出现了多少次
for i := 0; i < length; i++ {
if _, ok := m[s[i]]; ok {
m[s[i]] = m[s[i]] + 1
//如果一个字符出现了超过两次，说明该字符重复了
if m[s[i]] == 2 {
flag++
}
continue
}
m[s[i]] = 1
}
//如果没有重复的字符直接返回true
if flag == 0 {
return true
}
for i := length; i < len(s); i++ {
//新增的字符
if _, ok := m[s[i]]; ok {
m[s[i]] = m[s[i]] + 1
if m[s[i]] == 2 {
flag++
}
} else {
m[s[i]] = 1
}
//删除原来的字符
m[s[i - length]] = m[s[i - length]] - 1
if m[s[i - length]] == 1 {
flag--
}
if flag == 0 {
return true
}
}
return false
}
func lengthOfLongestSubstring(s string) int {
if len(s) <= 1 {
return len(s)
}
l, r, mid := 0, len(s), 0
//二分法找最大不重复子串
for l < r {
mid = (l + r + 1) >> 1
if judge(s, mid) {
l = mid
} else {
r = mid - 1
}
}
return l
}
解法二：
$O(n)$$O(n2)$出于好奇，我试了一下不使用二分法，顺序查找最大不重复子串，发现竟然耗时小于使用二分法，应该是测试数据的问题
func judge(s string, length int) bool {
flag := 0
m := make(map[byte]int)
for i := 0; i < length; i++ {
if _, ok := m[s[i]]; ok {
m[s[i]] = m[s[i]] + 1
if m[s[i]] == 2 {
flag++
}
continue
}
m[s[i]] = 1
}
if flag == 0 {
return true
}
for i := length; i < len(s); i++ {
//新增的字符
if _, ok := m[s[i]]; ok {
m[s[i]] = m[s[i]] + 1
if m[s[i]] == 2 {
flag++
}
} else {
m[s[i]] = 1
}
//删除原来的字符
m[s[i - length]] = m[s[i - length]] - 1
if m[s[i - length]] == 1 {
flag--
}
if flag == 0 {
return true
}
}
return false
}
func lengthOfLongestSubstring(s string) int {
if len(s) <= 1 {
return len(s)
}
l := -1
//顺序查找
for i := 0; i <= len(s); i++ {
if judge(s, i) {
l = i
} else {
break
}
}
return l
}
但是其实这种滑动窗口的方式不够优化，即使配合上二分法也只能达到nlogn的时间复杂度，我们可以再继续优化一下。
解法三：
map中记录的为最后一个字符出现的下标，每次当有新字符和之前的重复之后，就把last更新为最后一次出现的字符下标加1。
通过这种方式保证了当前窗口last到i不存在重复的字符
时间复杂度仅为O(n)
$O(1)$$O(n)$func find(s string) int {
last := 0
max := 0
m := make(map[byte]int)
for i := 0; i < len(s); i++ {
if _, ok := m[s[i]]; ok && m[s[i]] >= last {
last = m[s[i]] + 1
m[s[i]] = i
continue
}
m[s[i]] = i
if i - last + 1 > max {
max = i - last + 1
}
}
return max
}
func lengthOfLongestSubstring(s string) int {
if len(s) <= 1 {
return len(s)
}
return find(s)
}