1、无重复字符的最长子串
- 中等
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串的长度。
示例 1:
输入: s = “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3
示例 2:输入: s = “bbbbb” 输出: 1 解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
示例 3:
输入: s = “pwwkew” 输出: 3 解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。
class Solution:def lengthOfLongestSubstring(self, s: str) -> int:# 滑动窗口——左右指针：右指针遍历字符串，将子串放在结果集中# 当右指针指向的元素再一次出现在字符串中，就将左指针指向的元素移除直到右指针指向的元素不存在字符串中# 初始化结果，指针rns = set() # 将会实现去重l = 0res = 0for r in range(len(s)):while s[r] in rns:rns.remove(s[l])l+=1rns.add(s[r]) # 注意 set 是 add 方法，不是 appendres = max(res,r-l+1)return res 2、找到字符串中所有字母异位词
- 中等
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
示例 1:
输入: s = “cbaebabacd”, p = “abc” 输出: [0,6]
解释: 起始索引等于 0 的子串是 “cba”, 它是"abc" 的异位词。 起始索引等于 6 的子串是 “bac”, 它是 “abc” 的异位词。
示例 2:输入: s = “abab”, p = “ab” 输出: [0,1,2]
解释: 起始索引等于 0 的子串是 “ab”, 它是 "ab"的异位词。 起始索引等于 1 的子串是 “ba”, 它是 “ab” 的异位词。 起始索引等于 2 的子串是 “ab”, 它是 “ab”
的异位词。
class Solution:def findAnagrams(self, s: str, p: str) -> List[int]:res=[]lp=len(p)ls=len(s)s_list=[0]*26p_list=[0]*26if lp>ls:return resfor i in range(lp):p_list[ord(p[i])-ord('a')]+=1s_list[ord(s[i])-ord('a')]+=1if p_list == s_list:res.append(0)for i in range(lp,ls):s_list[ord(s[i])-ord('a')]+=1s_list[ord(s[i-lp])-ord('a')]-=1if p_list == s_list:res.append(i-lp+1)return res
