最长不含重复字符的子字符串
0 / 0 / 创建于 4年前 /
pardon110 的个人博客
题面
请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
示例
输入: "pwwkew"
输出: 3解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，”pwke” 是一个子序列，不是子串。
来源：力扣（LeetCode）
链接：leetcode-cn.com/problems/zui-chang...
分析
- 滑动窗口
- 双指针
- 哈希映射
上码
- 哈希检测到是否有相同值
- 无重复值，当前字符收录入哈希，右指针扩张
- 有则，右指针等待扩大边界，左指增长，同时哈希收缩
- 重复直到同值左侧耗尽，一轮循环时记录最大长度，本质 字典模拟双端队列
func lengthOfLongestSubstring(s string) int {
maxLen := 0
m := make(map[byte]struct{},0)
for left,right := 0,0; right < len(s); {
if _,ok := m[s[right]];ok {
delete(m, s[left])
left++
}else{
m[s[right]] = struct{}{}
right++
}
if right - left > maxLen {
maxLen = right - left
}
}
return maxLen
}小结
循环体内自增，可让边界在循环体内参与计算，合理避免越界
同队列，栈一样，哈希变量动态扩张与收缩，可作为临时辅助工具参与
本作品采用《CC 协议》，转载必须注明作者和本文链接
关于 LearnKu
粤公网安备 44030502004330号