题目描述
给定一个字符串 s
,请你找出其中不含有重复字符的 最长子串的长度。
示例 1:
输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 "abc"
,所以其长度为 3。
示例 2:
输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 "b"
,所以其长度为 1。
示例 3:
输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 "wke"
,所以其长度为 3。
请注意,你的答案必须是 子串 的长度,“pwke” 是一个子序列,不是子串。
提示:
0 <= s.length <= 5 * 104
s
由英文字母、数字、符号和空格组成
代码及注释
func lengthOfLongestSubstring(s string) int {
res := 0 // 初始化最长子串的长度为0
slow, fast := 0, 0 // 初始化两个指针slow和fast
m := map[byte]int{} // 创建一个字典,用于存储字符及其对应的索引
// 遍历整个字符串
for fast = 0; fast < len(s); fast++ {
// 如果当前字符已经在字典中
if val, ok := m[s[fast]]; ok {
// 更新slow指针,确保不包含重复字符
slow = max(slow, val + 1)
}
// 更新最长子串的长度
res = max(res, fast - slow + 1)
// 更新当前字符的索引
m[s[fast]] = fast
}
return res // 返回最长子串的长度
}
// 返回两个数中的最大值
func max(a, b int) int {
if a > b {
return a
}
return b
}
代码解释:
初始化:
res
初始化为0,用于存储最长子串的长度。slow
和fast
初始化为0,分别用作滑动窗口的起始和结束。m
是一个字典,用于存储字符及其在字符串中的最后一个索引位置。
遍历字符串:
fast
指针从0开始,向右移动。
处理重复字符:
- 如果当前字符
s[fast]
已经在字典m
中,则更新slow
指针的位置,使其不包含重复的字符。具体地,slow
被更新为val + 1
,其中val
是当前字符上次出现的索引。
- 如果当前字符
更新最长子串的长度:
- 每次迭代后,计算
fast - slow + 1
的长度,并与res
进行比较,取较大值。
- 每次迭代后,计算
更新字典:
- 在每次迭代中,将当前字符及其索引添加到字典
m
中。
- 在每次迭代中,将当前字符及其索引添加到字典
返回结果:
- 返回最长子串的长度
res
。
- 返回最长子串的长度
通过这种滑动窗口的方法,可以找到不包含重复字符的最长子串的长度。
本文含有隐藏内容,请 开通VIP 后查看