给定一个字符串 s , 请你找出其中不含有重复字符的 最长子串 的长度.- 维护一个已经出现过的字符集合;
- 移动右指针, 判断新字符是否已经出现;
- 如果已经出现, 循环移动左指针直到不再含有该字符
- 重新加入该字符
- 更新最大长度
Python 写法1 (滑动窗口模板, 推荐写法)
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
l = r = 0 # 窗口边界
used = set()
ans = 0
while r < len(s):
# 当右指针指向重复元素时, 一直移动左边界, 直到无重复
while s[r] in used: # 注意判断的是右边界, 移动的是左边界
used.remove(s[l])
l += 1
used.add(s[r])
ans = max(ans, r - l + 1)
r += 1
return ansPython 写法2 (优化)
- 优化: 直接移动 l 指针到重复字符的下一个位置, 减少 l 指针移动;
def lengthOfLongestSubstring(self, s: str) -> int:
used = dict()
l = r = 0 # [l, r] 闭区间
ans = 0
while r < len(s):
if s[r] in used and l <= used[s[r]]: # l <= used[s[r]] 的意思是重复字符出现在窗口内;
l = used[s[r]] + 1
ans = max(ans, r - l + 1)
used[s[r]] = r
r += 1
return ans其他算法笔记
LeetCode Hot 100 (32)
[中等, LeetCode] 三数之和 🔥
[中等, LeetCode] 下一个排列 🔥
[中等, LeetCode] 两数相加 🔥
[中等, LeetCode] 全排列 🔥
[中等, LeetCode] 全排列II 🔥
[中等, LeetCode] 删除链表的倒数第N个结点 🔥
[中等, LeetCode] 和为K的子数组 🔥
[中等, LeetCode] 在排序数组中查找元素的第一个和最后一个位置 🔥
[中等, LeetCode] 字母异位词分组 🔥
[中等, LeetCode] 找到字符串中所有字母异位词 🔥
[中等, LeetCode] 括号生成 🔥
[中等, LeetCode] 搜索旋转排序数组 🔥
[中等, LeetCode] 数组中的第K个最大元素 🔥
[中等, LeetCode] 最长回文子串 🔥
[中等, LeetCode] 最长连续序列 🔥
[中等, LeetCode] 电话号码的字母组合 🔥
[中等, LeetCode] 盛最多水的容器 🔥
[中等, LeetCode] 组合总和 II 🔥
[中等, LeetCode] 组合总和 🔥[困难, LeetCode] K个一组翻转链表 🔥
[困难, LeetCode] 合并K个升序链表 🔥
[困难, LeetCode] 寻找两个正序数组的中位数 🔥
[困难, LeetCode] 接雨水 🔥
[困难, LeetCode] 最小覆盖子串 🔥
[困难, LeetCode] 最长有效括号 🔥
[困难, LeetCode] 正则表达式匹配 🔥
[困难, LeetCode] 滑动窗口最大值 🔥
[困难, 牛客] 最小覆盖子串 🔥[简单, LeetCode] 两数之和 🔥
[简单, LeetCode] 合并两个有序链表 🔥
[简单, LeetCode] 有效的括号 🔥
[简单, LeetCode] 移动零 🔥