【力扣打卡系列】滑动窗口与双指针(无重复字符的最长子串)
坚持按题型打卡&刷&梳理力扣算法题系列，语言为go，Day7
无重复字符的最长子串
- 题目描述
- 解题思路
- 不含重复字符——》考虑使用哈希表来存储记录
- 为了提高效率也可以用数组，hash := [128]bool{} （因为存的是字符的ASCLL码，所以开128大小即可），布尔值用于存储当前右端点是否重复
- 核心思想：遍历右端点，固定右端点，滑动左端点，保证左边绝对没有跟右端点重复的字符（即以右端点为准），有的话就滑动左端点去重复
- 总的来说，右端点负责扩张长度，左端点负责控制去重，遍历完之后记录下来整个过程中最长的子串长度即可
- 代码参考
func lengthOfLongestSubstring(s string) int {
hash := [128]bool{}
left := 0
ans := 0
for right,value := range s{
for hash[value]{
hash[s[left]] =false
left++
}
hash[value] = true
ans = max(ans, right-left+1)
}
return ans
}
- tips（好精妙的一道题）
- hash := [128]bool{}可以开一个类似于哈希表功能的数组，因为可以存字符的ASCLL码所以设置为128，bool值代表当前值是否有重复的情况（false代表当前没有重复的情况）
- 更新方式为：遍历右端点，每次设置hash[value] = true，即每次遍历的时候都把右端点的值记录进去
- 子串长度的计算公式为：right-left+1