LeetCode讲解篇之3. 无重复字符的最长子串
文章目录
- 题目描述
- 题解思路
- 代码实现
题目描述
题解思路
因为我们需要求无重复字符的最长子串，这个我们首先需要想到使用滑动窗口，窗口内记录无重复的子串的所有字符，移动窗口的右边界时，发现当前字符在窗口内已经出现，则将窗口中和当前元素相同的元素和其前面的元素淘汰，保证窗口内的字符都是不重复的，我们只需要滑动过程中窗口的最大长度即可
代码实现
func lengthOfLongestSubstring(s string) int {
// 最终结果
ans := 0
// 窗口
win := map[byte]int{}
// 窗口的左边界下标
left := -1
for i := 0; i < len(s); i++ {
c := s[i]
// 如果当前字符在窗口中存在，并且下标合法
if idx, ok := win[c]; ok && idx > left {
// 设置窗口的左边界，相当于淘汰窗口中和当前元素相同的元素和其前面的元素
left = idx
}
// 设置当前字符的下标
win[c] = i
// 刷新结果的最大值
ans = max(ans, i - left)
}
return ans
}