- LeetCode Hot 100 是最常被考察的题目集合，涵盖了面试中常见的算法和数据结构问题。
- 刷 Hot100可以让你在有限的时间内集中精力解决最常考的问题。
- 不仅要写出代码，还要理解问题的本质、优化解法和复杂度分析。
滑动窗口
438. 找到字符串中所有字母异位词
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词的子串，返回这些子串的起始索引。不考虑答案输出的顺序。s 和 p 仅包含小写字母。
思路： 哈希表+滑动窗口。把待匹配的字符串用数组哈希化，左右指针滑动，右指针纳入元素，判断是否合法，不合法则移动左指针直到合法。若窗口合法，且长度相等，符合条件。
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
ans = [] # 存放结果答案
cnt = [0] * 26 # 小写字母，26个位置存放频率
for i in p:
cnt[ord(i)-ord('a')] += 1 # 待匹配的字符串字符频率
left = 0
for right in range(len(s)):
cnt[ord(s[right])-ord('a')] -= 1 # 右指针位置元素纳入窗口
while cnt[ord(s[right])-ord('a')] < 0: # 若有元素频率小于0，①不在待匹配字符串，②多次出现同一字符【都是有字符超了】
cnt[ord(s[left])-ord('a')] += 1 # 将左指针对应的元素释放，频率还回去
left += 1 # 左指针右移，左指针追右指针
if right - left + 1 == len(p): # 如果长度相等，加上前面都不小于0，符合题意
ans.append(left)
return ans
209. 长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的 子数组[numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
思路： 依次纳入窗口，判断窗口中子数组是否满足target，因为要找最小长度，满足则移动左指针，更新最小长度。时间复杂度O(n)，空间O(1).
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
if sum(nums)<target: return 0 # 不存在符合条件的子数组
total = 0
slow = 0
ans = float('inf')
for fast in range(len(nums)):
total += nums[fast] # 依次将元素纳入窗口
while total >= target: # 找最小数组，满足条件移动左指针
ans = min(ans, fast-slow+1) # 更新最小长度
total -= nums[slow]
slow += 1
return ans
76. 最小覆盖子串
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。
注意：
对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。
思路： 记录每个字符需要个数和总个数，不断扩展右边界，直到覆盖全部子串。覆盖全部子串后，再不断缩小左边界，直到找到覆盖的最小区间（其中之一）。记录区间是否需要更新，再缩小一步左边界。
class Solution:
def minWindow(self, s: str, t: str) -> str:
need = Counter(t) # 统计下需要的数出现频率（更新可能出现负数）
ans = (0, float('inf')) # 元组记录起始索引和长度
needcnt = len(t) # 总需要的数
left = 0
for right in range(len(s)): # 用enumerate()写会好看，扩展窗口
if need[s[right]] > 0: # 目标数，则总数减1
needcnt -= 1
need[s[right]] -= 1 # 字符记录到对应字典，减1
if needcnt == 0: # 满足覆盖的子数组条件
while True: # 试图移动左指针，缩小窗口
if need[s[left]] == 0:
break
need[s[left]] += 1 # 不是目标数，则左移左指针
left += 1
if right - left < ans[1] - ans[0]: # 将所有非目标数移除，得到一个最小区间
ans = (left, right) # 如果比之前记录的小，更新
need[s[left]] += 1 # 移动左指针，同时将needcnt也加个1
needcnt += 1
left += 1
return '' if ans[1]>len(s) else s[ans[0]: ans[1]+1] # 切片用法
链表
142. 环形链表Ⅱ
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
思路： 快指针2步，慢指针1步；快慢指针环中相遇，从相遇点到环入口，和从链表到环入口距离一样。时间复杂度O(n)，空间O(1).
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
fast = slow = head # 使用快慢指针
while fast and fast.next: # 确保下一个节点存在，否则无法访问其next
slow = slow.next # 慢指针每次走一步
fast = fast.next.next # 快指针每次走两步
if fast == slow: # 快指针在环中追到慢指针
slow = head # 重置慢指针的位置
while fast != slow:
slow = slow.next
fast = fast.next
return slow # 慢指针再次移动的位置即为入环index
递归
78. 子集
思路： 回溯。每次进入回溯函数，先将当前集合加入结果，再遍历该层元素加入，递归回溯。主要起始位置需要变。
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
self.ans = [] # 存放结果
self.backtracking(nums, 0, [])
return self.ans
def backtracking(self, nums, startIndex, path):
self.ans.append(path[:]) # 每次都想加入结果集
for i in range(startIndex, len(nums)):
path.append(nums[i]) # 往里新增该层的元素
self.backtracking(nums, i+1, path) # 递归进入下一层
path.pop()
回溯
17. 电话号码的字母组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
思路： 不同的按键是不同的层，作为参数传递。
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
if not digits: return [] # 处理空字符串
phone_map ={
'2' : 'abc',
'3' : 'def',
'4' : 'ghi',
'5' : 'jkl',
'6' : 'mno',
'7' : 'pqrs',
'8' : 'tuv',
'9' : 'wxyz'
}
self.ans = []
self.backtracking(phone_map, digits, 0, [])
return self.ans
def backtracking(self, phone_map, digits, startIndex, path):
if startIndex == len(digits):
self.ans.append(''.join(path))
return
letters = phone_map[digits[startIndex]]
for letter in letters:
path.append(letter)
self.backtracking(phone_map, digits, startIndex+1, path)
path.pop()
39. 组合总和
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。
思路：
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
self.ans = []
self.backtracking(candidates, target, [], 0)
return self.ans
def backtracking(self, candidates, target, path, startIndex):
if target == 0:
self.ans.append(path[:])
return
if target < 0:
return
for i in range(startIndex, len(candidates)): # 为了避免顺序不同元素相同的重复，还是按顺序选
path.append(candidates[i])
self.backtracking(candidates, target-candidates[i], path, i) # 可以被无限选取，所以用i不用i+1
path.pop()
131. 分割回文串
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
思路： 如果是回文串，则加入path。path长度达到字符串长度，找到一种方案。
class Solution:
def partition(self, s: str) -> List[List[str]]:
self.ans = []
self.backtracking(s, [], 0)
return self.ans
def backtracking(self, s, path, startIndex):
if startIndex >= len(s): # 超过长度则得到一种分割方法
self.ans.append(path[:])
return
for i in range(startIndex, len(s)):
if s[startIndex:i+1] == s[startIndex:i+1][::-1]: # 最佳实践，判断是回文串就写入
path.append(s[startIndex:i+1])
self.backtracking(s, path, i+1)
path.pop()
