题目描述
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串的长度。
注意区分子串和子序列。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
思路分析：
1.输入：字符串
2.目标：最长子串
3.困难: 会有重复的字符，这会导致子串无效，同时需要继续向后搜索。 滑动窗口就很适合这个问题。 重点是如何知道当前的字符是否出现过，有两个解决办法：1.使用一个数组来记录各个字符的频率，因为都是英文字符，那么就是ASCII码的范围，0-127.2.使用一个哈希表来记录
解法一（滑动窗口+数组记录频率）：
点击查看代码
func lengthOfLongestSubstring(s string) int {
if len(s) == 0 {
return 0
}
left, right := 0, 0
var freq [127]int
result := 0
for right < len(s) {
if freq[s[right]] == 0 { // 如果右侧字符未出现
freq[s[right]]++
right++
} else { // 否则，移动左指针
freq[s[left]]--
left++
}
result = max(result, right-left) // 更新最大子串长度
}
return result
}
解法二（滑动窗口+哈希表）：
点击查看代码
func lengthOfLongestSubstring(s string) int {
if len(s) == 0 {
return 0
}
charIndexMap := make(map[byte]int) // 哈希表存储字符的最新出现位置
maxLength := 0
left := 0 // 滑动窗口左边界
for right := 0; right < len(s); right++ {
// 如果当前字符在哈希表中存在，并且它的索引大于等于左边界，说明它重复了
if idx, found := charIndexMap[s[right]]; found && idx >= left {
left = idx + 1 // 将左边界移动到重复字符的下一个位置
}
// 更新当前字符的最新出现位置
charIndexMap[s[right]] = right
// 计算窗口的长度并更新最大长度
maxLength = max(maxLength, right-left+1)
}
return maxLength
}