HOT100 从 23 年开始零零散散做过，但其中 trick 与脑筋急转弯比较多，还是很容易忘，特此总结成复习笔记。
此外，还有些面试常见题也会写在后面。
和 ‘算法题 - 分类索引’ 有一定的重复。
HOT 100 的分类其实有点问题，暂时先按顺序写了，比如很多题的知识点和类别就关系不大。
哈希 #
题干：给一个数组，找的任意两数之和等于目标值
思路：一轮遍历，用哈希记录当前遍历过哪些数，然后当前元素查哈希表即可
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
m = defaultdict(lambda : -1) # 哈希表缺省值
n = len(nums)
for i in range(n):
if m[target - nums[i]] != -1:
return [i, m[target - nums[i]]]
m[nums[i]] = i
return []
题干：有字符串数组,对其中每个字符串按其中出现的元素分类
输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]
思路：对每个字符串排序后，哈希 key 为排序后的值
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
n = len(strs)
m = defaultdict(list)
for i in range(n):
tmp_s = ''.join(sorted(strs[i])) # 注意下 str 的 join 用法
m[tmp_s].append(strs[i])
ans = []
for i, v in m.items():
ans.append(v)
return ans
题干：给一个数组，找的其中所有元素排序后最长的连续序列
输入：nums = [100,4,200,1,3,2] 输出：4 解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
思路：不能使用排序。用桶重构数组，遍历每个连续序列的首值，记录每个序列的长度。最终使数组中每个元素最多遍历一边。
# 桶 + 技巧
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
m = set(nums)
ans = 0
for x in m: # !注意此处是在 set 中遍历，在 nums 中遍历最差是 On2
if x - 1 in m:
continue
xx = x
length = 0
while xx in m:
length += 1
xx += 1
ans = max(ans, length)
return ans
双指针 #
题干：不改变数组顺序去情况下，将零全部移动到末尾，要求操作次数最少
输入: nums = [0,1,0,3,12] 输出: [1,3,12,0,0]
思路：将一个指针视作栈顶，即目前有多少非零的数，栈顶一定指向零，当遍历到非零元素交换。
注意：和 荷兰国旗问题比较接近，但此题要求有序，因此解法不同。
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
n = len(nums)
stack_size = 0
for i in range(n):
if nums[i] != 0:
nums[i], nums[stack_size] = nums[stack_size], nums[i]
stack_size += 1
题干：找数组两个“隔板”之间能容纳最多的水，注意不同与接雨水，不用考虑“隔板”本身的体积。
输入：[1,8,6,2,5,4,8,3,7] 输出：49
思路：双指针从两边向中间走，哪边数小就缩哪边
class Solution:
def maxArea(self, height: List[int]) -> int:
n = len(height)
l = 0
r = n - 1
ans = 0
while l < r:
ans = max(ans, (r - l) * min(height[l], height[r]))
if height[l] < height[r]:
l += 1
else:
r -= 1
return ans
题干：记录数组中所有 x + y + z == 0 的值，需要去重。
思路：排序后三指针，遍历 x 作为基数，由于 y 和 z 一定有序，还是从两边缩小到中间的思路。此外可以遍历过程中去重，也可以用 tuple 做 hash 的 key，后者思维量小。
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
nums.sort()
ans = set()
for i, x in enumerate(nums):
l = i + 1
r = n - 1
while l < r:
if nums[l] + nums[r] == -x:
ans.add((nums[i], nums[l], nums[r]))
# break
# 注意下此处不能直接 break，因为同一个 i，可以对应不同的 l r 做答案
l += 1
r -= 1
elif nums[l] + nums[r] < -x:
l += 1
else:
r -= 1
res = []
for x in ans:
res.append([x[0], x[1], x[2]])
return res
题干：过于经典，不赘述了
思路：
- 前缀后缀法：通法，思维量较小。统计每个数的最大前后缀
- 双指针实际上就说前缀后缀的优化版，核心就是哪侧前或后缀更小，就缩那测
- 单调递减栈，找上一个更大的，然后填坑
# 前缀后缀
class Solution:
def trap(self, height: List[int]) -> int:
n = len(height)
pre = [0] * n
pre[0] = height[0]
suf = [0] * n
suf[-1] = height[-1]
for i in range(1, n):
pre[i] = max(pre[i - 1], height[i])
for i in range(n - 2, -1, -1):
suf[i] = max(suf[i + 1], height[i])
ans = 0
for i in range(n):
ans += (min(pre[i], suf[i]) - height[i])
return ans
# 双指针，谁小谁移动
class Solution:
def trap(self, height: List[int]) -> int:
n = len(height)
l = 0
r = n - 1
pre_max = height[l]
suf_max = height[r]
ans = 0
while l < r:
if pre_max < suf_max:
ans += (pre_max - height[l])
l += 1
else:
ans += (suf_max - height[r])
r -= 1
pre_max = max(pre_max, height[l])
suf_max = max(suf_max, height[r])
return ans
# 单调栈做法
class Solution:
def trap(self, height: List[int]) -> int:
stack = []
n = len(height)
ans = 0
for i, x in enumerate(height):
while stack and x >= height[stack[-1]]:
bottom = height[stack[-1]]
stack.pop()
if not stack:
break
l = stack[-1]
h = min(height[l], x) - bottom
ans += h * (i - l - 1)
stack.append(i)
return ans
滑动窗口 #
题干：找到数组中无重复字符的最长子串
思路：滑动窗口 + 哈希的模板题
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
n = len(s)
m = defaultdict(int)
l = r = ans = 0
while l <= r and r < n:
m[s[r]] += 1
# print(m)
while l <= r and m[s[r]] != 1:
# print(l, r, m)
m[s[l]] -= 1
l += 1
ans = max(ans, r - l + 1)
r += 1
return ans
题干：找到数组中所有 “目标字符 cnt ”等于”字串字符 cnt“ 的字串下标
思路：稍微变形的滑窗板子，注意当缩减左窗口后，字串长度与目标相同时，一定两者 cnt 相同。
# 滑动窗口板子
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
n = len(s)
l = r = 0
t = defaultdict(int)
for i in list(p):
t[i] += 1
m = defaultdict(int)
ans = []
while l <= r and r < n:
m[s[r]] += 1
while l <= r and m[s[r]] > t[s[r]]: # 注意下缩左窗口的条件
m[s[l]] -= 1
l += 1
# print(r, l, m)
if r - l + 1 == len(p):
ans.append(l)
r += 1
return ans
字串 #
题干：找子串和为 K 的数量
思路：O1 求区间和 -> 需要前缀和 -> 哈希记录出现的指定前缀数量 -> 和两数之和思路一样
# 求区间和 -> 前缀和 -> 哈希记录出现的指定前缀数量
class Solution:
def subarraySum(self, nums: List[int], k: int) -> int:
n = len(nums)
prefix = [0] * (n + 1)
m = defaultdict(int)
m[0] = 1
ans = 0
# prefix[x] - prefix[y] == k
# 即找 m[prefix[i] - k] 的数量
for i in range(1, n + 1):
prefix[i] = prefix[i - 1] + nums[i - 1]
ans += m[prefix[i] - k]
m[prefix[i]] += 1
return ans
题干：找所有定长字串的最大值，要求 On
思路：经典单调队列，仅字串中保持递减的一个队列，右侧插入与单调栈一致。当左侧和首元素下标相同时，队列进行 O1 移除。从而使每个队列的首元素一定是当前字串的最大值。
单调队列相比单调栈出现的更少，注意其基本都是在栈中存下标，然后注意栈中的严格单调性。
此外，此题还有个 ST 表 做法，但复杂度不比单调队列好。
# 单调队列
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
arr = deque()
n = len(nums)
r = 0
ans = []
while r < n:
# print(r, arr)
if r >= k:
ans.append(nums[arr[0]])
if arr[0] == r - k: # 维护左下标
arr.popleft()
while arr and nums[r] >= nums[arr[-1]]: # 入队列操作和单调栈一样
arr.pop()
arr.append(r)
r += 1
ans.append(nums[arr[0]])
return ans
题干：找到所有字串中，“目标串元素 cnt “ 能覆盖的”长度最小字串元素 cnt “是什么？
输入：s = “ADOBECODEBANC”, t = “ABC” 输出：“BANC”
思路：如果只要 O(52*n) 即滑窗的过程每次遍历单词表，那就是滑窗板子，和438. 找到字符串中所有字母异位词 完全一样。
但如果想 O(n) 还是有些难度，新提出一个 less 字符标志，判断单词表中有多少词仍未被覆盖，从而代替遍历单词表。
但要注意 less 的维护方法。
class Solution:
def minWindow(self, s: str, t: str) -> str:
n = len(s)
l = r = 0
target = defaultdict(int)
for i in list(t):
target[i] += 1
m = defaultdict(int)
less = len(target) # 开始时 target 中每个词都没被满足
ans_l, ans_r = 0, inf
while l <= r and r < n:
m[s[r]] += 1
if m[s[r]] == target[s[r]]: # 注意此处一定是等于，只想让 less 更新一次
less -= 1
while l <= r and less == 0:
# print(l, r, less, ans_l, ans_r)
if (ans_r - ans_l) > (r - l): # 注意此时内层循环才满足答案吗要求
ans_l = l
ans_r = r
m[s[l]] -= 1
if m[s[l]] == target[s[l]] - 1:
less += 1 # 同样的，保证 less 只更新一次
l += 1
r += 1
return s[ans_l:ans_r + 1] if ans_r != inf else ""
普通数组 #
题干：找字串中最大的 sum 是多少？
思路：前缀和 + 空间优化（也可以简单 DP）。记录前缀和的最小值即可，简单优化下就能空间 O1。
# 找个前缀就可以
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
n = len(nums)
prefix = 0
pre_min = inf
ans = -inf
for i in range(1, n + 1):
pre_min = min(prefix, pre_min)
prefix = prefix + nums[i - 1]
ans = max(ans, prefix - pre_min)
return ans
题干：合并所有有重叠的区间
思路：对原始区间排序后，比较当前区间的右侧和下一个区间的左侧。大部分语言之间排就可以，小部分要写 lambda。
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
intervals.sort()
ans = []
l = intervals[0][0]
r = intervals[0][1]
for x, y in intervals:
if x <= r:
r = max(y, r)
else:
ans.append([l, r])
l = x
r = y
ans.append([l, r])
return ans
题干：将数组右移动 k 位
思路：三次反转，先转最大区间，再转两个小区间
提示：如果是左移，其实就等于右移 -k 位
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
# 自带的 reverse 会产生多余空间，自己用双指针搓更合适
def reverse(l, r):
while l < r:
nums[l], nums[r] = nums[r], nums[l]
l += 1
r -= 1
n = len(nums)
k %= n
reverse(0, n - 1)
reverse(0, k - 1)
reverse(k, n - 1)
题干：获得每个数对应的除了他自己以外全部元素的乘积。
思路：明显的前后缀，题目要求只使用一个额外数组，先后缀后前缀直接得到答案就可以
# 前缀后缀积，最好用一个数组解决
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
n = len(nums)
suf = [1] * n
for i in range(n - 1, 0, -1):
suf[i - 1] = suf[i] * nums[i]
# print(suf)
pre = 1
for i in range(n):
suf[i] *= pre
pre *= nums[i]
return suf
题干：找数组中没出现的最小正数，要求 O(n) 时间，O1 空间。
思路： 经典技巧题，想让每个符合条件的位置满足 nums[i] == nums[nums[i]]。
这样就相当于让位置 i 的 x 一定回到 x 的位置上，此外交换过程中要考虑 swap 依赖问题。
class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
n = len(nums)
for i in range(n): # 对齐下标
nums[i] -= 1
for i in range(n):
while 0 <= nums[i] < n and nums[i] != nums[nums[i]]:
j = nums[i] # 要让 swap 不被依赖
nums[i], nums[j] = nums[j], nums[i]
# print(nums)
for i in range(n):
if nums[i] != i:
return i + 1
return n + 1