Leetcode 无重复字符的最长子串
无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
我的思路 & 实现
使用两个指针，分别为头指针和尾指针。
- 头指针指向无重复字符子串头部，一个指向子串尾部，初始时，两个指针都指向字符串第一个元素。
- 维护一个哈希表（查找效率高），存放当前子串已有元素
- 尾指针检查当前所指元素是否在当前子串中出现过（查找哈希表中是否有当前元素），如果不存在，将当前元素存入哈希表，尾指针后移，并更新最大长度；如果存在，说明已经找到了一个无重复字符的子串，可以找下一个了，移动头指针到与当前尾指针相同的元素之后，置尾指针等于头指针，清空当前哈希表，重复上述操作。
- 当遍历完字符串，就会得到答案
代码
func lengthOfLongestSubstring(s string) int {
if len(s) == 0 {
return 0
}
hashMap := make(map[byte]int)
leftP := 0
rightP := 0
result := 1
for rightP < len(s) {
_, ok := hashMap[s[rightP]]
if !ok {
hashMap[s[rightP]] = 1
rightP++
if (rightP - leftP) > result {
result = rightP - leftP
}
}else{
for s[leftP] != s[rightP] {
leftP++
}
leftP++
rightP = leftP
hashMap = make(map[byte]int)
}
}
return result
}但是性能表现却很差
执行用时：260 ms, 在所有 Go 提交中击败了5.16%的用户
内存消耗：6.8 MB, 在所有 Go 提交中击败了5.34%的用户
通过测试用例：987 / 987这是滑动窗口的一般思路，题解也是这个做法，不懂为何性能这么差！
优化
优化了之前的代码，性能大大提高
- 之前的代码在找到一个无重复字符子串后，采用make重新创建一个map的方法来清空原map，这个操作是费时的
- 由于采用了创建新的map来清空map，导致尾指针在寻找下一个无重复字符子串时需要返回到与头指针一样的位置，这样就多了不必要的遍历，以及往map中添加元素的操作，很费时
- 在已经找到一个无重复字符子串之后，在头指针右移的过程中，同时删除map中相关的元素
- 这样就不需要新创建一个新map，也大大减少空间复杂度，同时尾指针也不需要返回到头指针处，而是直接在它的当前位置继续移动，大大减少时间复杂度
func lengthOfLongestSubstring(s string) int {
if len(s) == 0 {
return 0
}
hashMap := map[byte]int{}
leftP := 0
rightP := 0
result := 1
for rightP < len(s) {
if hashMap[s[rightP]] == 0 {
hashMap[s[rightP]]++
rightP++
if (rightP - leftP) > result {
result = rightP - leftP
}
}else{
for s[leftP] != s[rightP] {
// 头指针移动的同时删除map中相应元素
delete(hashMap, s[leftP])
leftP++
}
delete(hashMap, s[leftP])
leftP++
}
}
return result
}性能
执行用时：12 ms, 在所有 Go 提交中击败了40.79%的用户
内存消耗：2.6 MB, 在所有 Go 提交中击败了67.64%的用户
通过测试用例：987 / 987本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2023-04-27，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
