此处记录自己刷算法八股中的灵感，不会的题在此写下自己的感受和解题方法。目录的标题是主要使用的算法。
ref: LeetCode 热题100
哈希
复杂度为$O(n)$时常用，作用：$O(n)$建立，$O(1)$查找
对应的Python容器：dict(), collections.defaultdict()（即查找不到key时设置一个默认返回value）
最长连续序列（longest consecutive sequence）
题目要求：给定一个整数数组，在其中找到最长的连续序列的长度（数字的位置不一定相邻）。要求线性复杂度。
示例：
输入：nums=[100,4,200,1,3,2]
输出：4
解释：4, 1, 3, 2是最长的连续序列，长度为4。
思路：好吧真没啥思路……排序算法就得吃掉$O(n\mathrm{log}n)$的复杂度；但是一个个找升序元素的话最终会消耗$O(n^2)$，铁铁的TLE
看完题解的哈希表后自信满满地选择性添加键值对（即x若在字典中没有键x-1则添加键x），在用例[0,-1]时报错……崩溃了
题解：（内心OS这也能哈希？）既然要找升序元素，那么哈希表就可以很方便找啦。把数组中的一些元素哈希到表里√
但是如果对每个元素x都要找x+1，那么又回到了上面的“一个个找元素”，复杂度仍是平方。既然题目只要求输出长度，那么直接用长度作为哈希表的值就可以啦！目标就是构建字典{x: x开始的最长连续序列长度}。为了摆脱“对每个x都要找元素”，我们加入判断：对于每个x，它是否是序列开始的元素？若是，则x往后的元素对应的值都+1；否则，x对应的值先默认为1。
首先将数组哈希一遍，并让哈希表的值全1；然后遍历哈希表，若x在哈希表中有对应的元素x-1，则键x对应的值+1，且键x+1, x+2……对应的值也+1，直到键不存在。
代码：
class Solution:
def longestConsecutive(self, nums: list[int]) -> int:
arr = {} # arr[nums中的数字]=从它开始的最长连续序列长度
nums = list(set(nums)) # 去重
for i in nums:
arr[i] = 1 # 默认从i开始的排列长度为1
for i in nums:
if i-1 not in arr.keys(): # 如果是开头
next = i+1
while next in arr.keys():
arr[i] += 1
next += 1
return max(arr.values())
双指针
用两个或多个指针实现数组的遍历任务。
三数之和（3Sums）
题目要求：给定一个整数数组，找出数组中所有的三个数之组合，使其和为零。输出中不能出现重复的组合。
示例：
输入：nums=[-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
思路：虽然感觉会TLE但还是大胆地写了三重循环（每重循环找一个数），果然在nums长度为3000时炸了；后来发现可以固定第一个数，并循环地找剩下两个数，但天真的自己还没发现这就是上面的解法全体目光向我看齐，我宣布个事后来看了题解还能先排序的？，可以先固定第一个数，将后两个数的寻找过程合并成$O(n)$的遍历任务，左右指针相逢即结束寻找，并向后推进第一个数。
然而写了一天了还没发现，寻找后两个数时我还在不自觉地重复遍历后半段的数组，让后两个指针相逢后又回到两边，重复着一遍遍的相逢……这么$O(n^3)$的算法我还在挠头为什么会TLE
题解：三重循环直接TLE（在长度为3000的数组中寻找组合用了75s之久），故我们需要找到复杂度小于$O(n^3)$的算法；注意到排序算法的开销为$O(n \mathrm{log}n)$，在无限渐进中是小于$O(n^2)$的，故可以先对数组排序以方便处理。
排序后从头固定第一个数，且让第二个数的指针放在第一个数后。将第三个数放在尾端，寻找后两个数时，让两个指针慢慢靠近即可。其实，固定好第一个数后，后两个指针总共只需要遍历一次后半段数组，这样单次循环的复杂度即可降至$O(n)$；外围套上第一个数的遍历，总复杂度为$O(n^2)$。
如何遍历后两个指针？三个指针的数字之和若大于零，则说明需要调小第三个指针，让它左移即可；不断左移，直至三数之和不大于零。若和为零则添加进组合中；若小于零，则说明第三个指针不能再往左移了（这样和只会更小），需要移动的是第二个指针。如此操作，即可让两个指针逐渐相逢，并结束单次循环。
考虑到有序数组中可能出现重复数字序列，移动第二个指针时需要注意将其移至重复序列的末端。
代码：
class Solution:
def threeSum(self, nums: list[int]) -> list[list[int]]:
res = []
nums.sort() # 排序，用时O(nlogn)
n = len(nums)
# 保证输出的三元组是按升序排列
fir, sec, thi= 0, 1, 2 # 这是第一、二、三小的元素的位置
while fir < n:
if fir == 0 or nums[fir] != nums[fir-1]: # 每次循环里，第一小的元素都要不同；而且可保证fir指向相同数字序列的开头
# 先指定sec在fir的下一个位置，thi在数组末端
sec = fir + 1 # sec指向的数字不能小于fir
thi = n - 1
while sec < n: # 要保持sec在thi的左边，两个指针碰面/擦过即代表列举完成
if sec == fir + 1 or nums[sec] != nums[sec-1]: # 每次循环里，第二小的元素都要不同；而且可保证sec指向相同数字序列的开头
if sum([nums[fir] + nums[sec] + nums[thi]]) > 0:
while sum([nums[fir] + nums[sec] + nums[thi]]) > 0 and thi > sec:
thi -= 1 # 如果和大于零，则左移最大的指针，使其靠近零
if not thi > sec >= 1: break
if sum([nums[fir] + nums[sec] + nums[thi]]) == 0:
res.append([nums[fir], nums[sec], nums[thi]])
sec += 1
fir += 1
return res
用上平方复杂度的算法后，运行时间砍到百分之一，看到0.7s的那时刻直接震撼我一整年了
说起来我这段python代码咋一股子C味
子串
若需要子串中的最值元素，可以考虑用根堆/队列。
对应的Python容器：heapq（搭建小根堆，以数组形式保存二叉树）, collections.deque()（双端队列）
和为K的子数组（Subarray Sum Equals K）
题目要求：给定一个整数数组，输出和为K的子数组的个数。
示例：
输入：nums = [1,1,1], k = 2
输出：2
输入：nums = [1,2,3], k = 3
输出：2
思路：依旧尝试逐渐调大窗口，每个窗口尺寸依旧遍历sum()，$O(n^3)$算法果然炸裂（自己的电脑在长度为20000的数组中等了很久没跑出来结果）；后来发现窗口尺寸固定的时候，滑动窗口时没必要每滑一步都sum()一遍，遂改为“每个尺寸的窗口在最开始的位置求和，向右滑动时只要在和中减去前一个数、加上窗口后一个数”。
不知为何仍旧TLE，但是在自己的电脑上跑出结果了（仅19s）……不过我确实想不到怎么优化算法了
题解：第一种方法也是逐渐调整窗口，但并不是“尺寸慢慢调大”，而是让每一次的循环都固定右边界i，让左边界j从右边界i逐渐靠近开头；在每次内层循环中，左边界j每次左移一格时，扫过的一个数字都加入总和并判断是否为K。外层循环中，右边界i从头至尾遍历即可。（虽然复杂度$O(n^2)$，但官方题解中没给出python代码，然后自己用python照着写果断TLE这就是py的计算性能吗）（而且用这个方法在自己的电脑上能砍掉一半运行时间欸）
可能是因为py效率不够？官方针对上面的题解做出了优化还能优化到线性复杂度的我草。为了避免每次向左拉窗口时的重复求和，我们需要用到一个叫前缀和的东西。
定义：$pre(i)$为数组nums[0...i]的和，即i本身对应元素以及i之前的所有元素之和。上面的解法中，当窗口中的和为K时，可以用前缀和的方式写作
$$
pre(i)-pre(j-1)=K
$$
那么问题就变成了如何寻找满足上述等式的i与j，并记录这样的(i, j)有多少对。对上述等式移项可得
$$
pre(j-1)=pre(i)-K
$$
我们创建字典{前缀和: 这样的前缀和有多少个}。当i=0, 1, 2…时，在字典中找键$pre(i)-K$对应的值，即可找到前缀和为$pre(j-1)$的j有多少个，于是我们在每次外循环中把对应的值累加起来，就能得知有多少对(i, j)满足等式。我们注意到这样的字典是可以随着i的右移动态创建的，而且这样的创建可以保证0<=j<i：
from collections import defaultdict
prefixcount = defaultdict(int) # 当键不存在时则默认值为0，这也能对上上面字典的定义
pre = 0
for i in range(len(nums)):
pre += nums[i] # 每次循环中直接计算pre(i)
prefixcount[pre] += 1
每次循环中，再加入检测字典中键$pre(i)-K$对应的值，计入count，即count += prefixcount[pre-K]。
用第二种方法的时间复杂度为$O(n)$，其中i从左遍历到右复杂度为$O(n)$，而每次循环中只需要用常数复杂度就能得知满足公式的(i, j)的对数。
代码：
class Solution:
# 这是第一种解法，但是用python运行会在大数组下TLE；用C++重写一遍会更好
def subarraySum(self, nums: list[int], k: int) -> int:
count = 0
for start in range(len(nums)): # start在窗口右端
sum = 0
for end in range(start,-1,-1): # end从start的地方向左拉开窗口
sum += nums[end]
if sum == k: count+=1
return count
# 第二种解法
def subarraySum2(self, nums: list[int], k: int) -> int:
count = 0
from collections import defaultdict
prefixcount = defaultdict(int) # 计算前缀和为*键*的位置有多少个（即对应的值）
pre = 0 # 这个作为题解中的pre(i)
for start in range(len(nums)):
prefixcount[pre] += 1 # 这里第一次运行会有prefixcount[0]=1，这是为了防止pre-k=0（i及之前的所有元素加起来为k）时，count不能+1
pre += nums[start]
count += prefixcount[pre-k] # 在count上积累：前缀和为pre(i)-K的j的位置个数
return count
用第二种方法，数组长度两万时只用了0.00s就跑完了（？！
依旧震惊一整年
滑动窗口最大值（Sliding Window Maximum）
题目要求：给定数组nums与数字k，长为k的窗口从左至右遍历nums，求每个窗口中的最大值。
示例：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置 | 最大值
[1 3 -1] -3 5 3 6 7 | 3
1 [3 -1 -3] 5 3 6 7 | 3
1 3 [-1 -3 5] 3 6 7 | 5
1 3 -1 [-3 5 3] 6 7 | 5
1 3 -1 -3 [5 3 6] 7 | 6
1 3 -1 -3 5 [3 6 7] | 7
思路：暴力解（每个窗口都max一遍）果断在数组长度十万、窗口长度五万时TLE（本地电脑用时26s）；注意到滑动一次窗口时中间数组的大部分元素都不用重新max，于是寻思能不能用一个指针firstmax做标记，然后滑动窗口后直接拿末尾元素与firstmax作比较……
然后滑动窗口时发现，如果滑动前指针在最左侧，那么滑动后又要重新找一遍窗口内最大值；于是再加一个第二大的指针secndmax，标注窗口内第二大的元素（这样出现上述情况就不用再找一遍最大值，直接用secndmax就行）。
但是又发现，如果滑动前secndmax在最左侧，滑动后第二大指针丢掉了，是不是又要找一遍第二大的元素呢……再加一个第三大的指针？nonono
题解：python还自带根堆结构？我说python王朝了有没有懂的
上面的暴力解中，每次max可以换成搭建大根堆，取根就可以得到最大元素。滑动窗口时，往堆中放入后一个元素，并判断堆中是否还有窗口前的元素更大，若有则移除掉。
但是嘛……滑动窗口时中间大部分元素都不用再比较一遍的，有没有更快的方法呢？
第二种方法：双端队列。python怎么还有队列？具体操作如下（题解的证明我实在看不懂了）：
– 向右展开窗口时，比较队尾与即将进入窗口的元素：若队尾小于等于待进者，则不断踢掉队尾，直至队尾严格大于待进者，让待进者入队。
– 窗口展开到k时，将队头元素加入输出结果（这是第一个窗口的最大值；我们需要保证队中的元素是严格递减），并开始向后移动窗口。
– 移动窗口时，仍重复第一步的操作（最严苛的情况下待进者能够让队清空，总之待进者是要入队的）；此时加入判断，若队内有窗口外的元素，则从队头清出，直至队头的元素在窗口内。（可以看到构造队列时这个队的下标是递增的，只需q.popleft()即可）
题解评论区有个深刻的比喻：我们将队列看成公司，数组的元素是一个个要进公司的员工。窗口则为“适合工作”的年龄窗口。
– 员工进公司时，若新来的员工（待进者）实力比队尾的员工强，则从队尾一个个末尾淘汰，直至队尾员工严格强于待进者，招入新人。
– 随着老员工（队头元素）的年龄增长，若员工超龄（从左边掉出窗口），则不断地开除队头，直至队头员工更年轻（在窗口内）。
– 队尾比不过年轻同龄人的，踢出公司；队头年龄太老超出时代区间的，踢出公司。
总结：谁教你这么比喻的？看来得卸载力扣准备粉笔了
代码：
class Solution:
# 第一种方法：根堆
def maxSlidingWindow(self, nums: list[int], k: int) -> list[int]:
import heapq # python的小根堆实现方式
res = []
n = len(nums)
justaheap = [(-nums[i], i) for i in range(k)] # 列表，保存元素和对应位置。注意：python只能搭小根堆，故每个元素取反
heapq.heapify(justaheap) # 把列表转化成了小根堆。这个变量其实还是列表，但元素顺序排列成了对应的完全二叉树数组。
res.append(-justaheap[0][0]) # 取第一个元素就是小根堆的根，即最小元素；对其取反，就得到了第一个窗口中的最大元素
for i in range(k, n):
heapq.heappush(justaheap, (-nums[i], i)) # 滑动窗口时，把末尾的元素放进堆
while justaheap[0][1] <= i-k: # 如果最小的元素存在于窗口前面，等价于heapq.nsmallest(1, justaheap)[1] <= i-k
heapq.heappop(justaheap) # 就把根弹出去
res.append(-justaheap[0][0]) # 把小根堆的根取反后加入输出结果
return res
# 第二种方法：裁员广进
def maxSlidingWindow2(self, nums: list[int], k: int) -> list[int]:
from collections import deque # 双端队列的实现方式
res = []
n = len(nums)
q = deque()
# 每次滑动窗口时，这个队列中的队首保存窗口中最大的元素下标
# 注意要踢掉不在窗口中的元素。
for i in range(k):
while q and nums[i] >= nums[q[-1]]:
q.pop()
q.append(i)
res.append(nums[q[0]])
for i in range(k,n):
while q and nums[i] >= nums[q[-1]]: q.pop() # 确保每次队列中的下标升序排列，且下标对应的元素严格降序排列
q.append(i) # 将窗口右端加入队列
while q[0] <= i-k: q.popleft() # 如果最大元素的下标在窗口之前，则从左边踢掉它，直至最大元素的下标在窗口内
res.append(nums[q[0]])
return res
第一种方法复杂度为$O(n \mathrm{log}k)$：滑动窗口需要用掉$O(n)$，每次调整根堆需要用掉$O(\mathrm{log}k)$。在上述极端用例中，运行时间骤降至0.03s。
第二种方法复杂度为$O(n)$：每个下标只有一次“入职”，且几乎必有一次“毕业”。互联网现状，唉
数组
相关思路：“从头/尾开始的统计量”。例如从头/尾开始的数组和等等。
相关排序：List.sort(key: Callable) -> None可让列表依据给出的函数排序。
最大子数组和（Maximum Subarray）
题目要求：给定整数数组nums，返回最大的子数组之和。
示例：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
思路：尝试滑动窗口，先让指针放置在头尾两侧，然后让左右指针滑动到下一个非负数的位置计算和，结果被各种边界条件坑死（全非正数、滑动的时候正好错过最大值等等……）；看到可以用分治求解，想当然地认为在左右两半数组的最值与两半数组之和取最大，果断寄。
反思了下，左右两半数组要传回来对应的指针，这个应该有用；遂改为在两个子数组的最值与“左半段的开头~右半段的末尾”取最值，直接死循环（想想如果数组只有两个元素）
题解：滑动窗口是好的，但是我们引入带后缀最大和的概念：即以第i个元素为末尾，满足此条件的所有子数组中的最大和（记为$f(i)$）。于是问题变为如何寻找这样的i。
可以从头开始动态地求$f(i)$：
– $f(0)$就是nums[0]。
– 对于$f(i)， i>0$时则在$f(i-1)$+num[i]与num[i]中挑较大者。即maxSumFromEnd = max(maxSumFromEnd+num, num)。
题目其实还有个可选要求：分治法？把数组拆成前后两半也是好的，但是每个子数组要维护四个统计量啊？：
带“头”的子数组中的最大和、带“尾”的子数组中的最大和、整个数组中的最大子数组和、整个数组的和。
对于只有一个元素的数组而言，这四个统计量都是一样的（就是这个元素）；合并维护时，
– 带“头”的子数组中的最大和，要么就是左半段中的带“头”的子数组中的最大和，要么就是整个左半段，加上右半段中带“头”的子数组中的最大和。
– 带“尾”的子数组中的最大和，要么就是右半段中的带“尾”的子数组中的最大和，要么就是整个右半段，加上左半段中带“尾”的子数组中的最大和。
– 整个数组中的最大子数组和，要么是前两项，要么是左半段中带“尾”的子数组中的最大和+右半段中带“头”的子数组中的最大和。
– 整个数组的和，即左半段和+右半端和。
代码：
class Solution:
def maxSubArray(self, nums: list[int]) -> int:
n = len(nums)
if n == 1: return nums[0]
maxSumFromEnd = nums[0] # “从最后一个元素开始往前计算”的最大子数组和，这个和对应的子数组要包含尾部
res = nums[0]
for num in nums[1:]: # 尾部开始移动
# 每个循环内，maxSumFromEnd都会随着下标的增加而改变
maxSumFromEnd = max(maxSumFromEnd+num, num) # 当前的“从元素num开始，返回到头部”的最大子数组和。要么是等于上一个最大和+num（把尾巴加上），要么就是单独的num
res = maxSumFromEnd if maxSumFromEnd > res else res
return res
def maxSubArray2(self, nums: list[int]) -> int:
n = len(nums)
if n == 1: return nums[0]
def maxSub(left, right): # 从left到right的最大子数组和
if left == right: return nums[left], nums[left], nums[left], nums[left]
# 返回的值：从最左端开始的子数组的最大和、从最右端开始的子数组的最大和、整个区间的最大子数组和（不限制左右条件）、整个区间的和
mid = (right - left) // 2
infoleft, inforight = maxSub(left, left+mid), maxSub(left+mid+1, right) # 左半段与右半段的信息
maxSumFromLeft = max(infoleft[0], infoleft[3]+inforight[0]) # 从最左端开始的子数组的最大和，要么是左半段数组的从左开始的子数组，要么是左半段全部和+右半段从左开始的子数组
maxSumFromRight = max(inforight[1], inforight[3]+infoleft[1]) # 从最右端开始的子数组的最大和，要么是右半段数组的从右开始的子数组，要么是右半段全部和+左半段从右开始的子数组
maxSum = max(infoleft[2], inforight[2], infoleft[1] + inforight[0]) # 最大子数组和，可能跨两半数组（左半段的从右开始+右半段的从左开始），也可能全在左半段，也可能全在右半段
allSum = infoleft[3] + inforight[3] # 整个数组的和就是左右两半数组的和
return maxSumFromLeft, maxSumFromRight, maxSum, allSum
return maxSub(0, n-1)[2]
第一种方法复杂度为$O(n)$。第二种方法，合并两段子数组的次数为$O(\mathrm{log}n)$，每次合并两段总长为$i$的数组时需要花费$O(1)$的复杂度（可以看到递归之外的执行次数与子数组规模无关）。运用主定理公式，$T(n)=2T(n/2)+O(1)=O(n)$。
主定理公式（Master Theorem）：涉及递归问题，分析复杂度时常用。
若$T(n)=aT(n/b)+O(n^d)$，其中$a$为调用子问题的数量，$b$为子问题缩小规模的比例，$d$为递归之外所需复杂度的参数，则：
* $d<\mathrm{log}_ba$时，总复杂度为$O(n^{\mathrm{log}_ba})$
* $d=\mathrm{log}_ba$时，总复杂度为$O(n^d{\mathrm{log}n})$
* $d>\mathrm{log}_ba$时，总复杂度为$O(n^d)$
合并区间（Merge Intervals）
题目要求：给定区间列intervals，其中每个元素为一个区间；输出这些区间取并的结果。
示例：
>输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]。
输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
思路：经过上一题的拷打自然而然地想分治，但是卡在了如何合并两个升序区间列……亏我还花了老大劲写俩区间合并的函数（不过看了题解发现复杂度都是$O(n \mathrm{log}n)$，至少我还没往蠢死的方向做无用功）
题解：不是怎么这会不分治了？对区间列以左端升序排序。这样有重叠的区间就一定是连续的（或者说，不存在某对有重叠的区间元素，是被不与其重叠的区间元素隔开的）。
说人话！左端点相同的区间列，可能与下一个这样的区间列重叠；若当前区间列的尾不与下一个列的头重叠，则下一个列都不与上一个列重叠，且之后的区间列也不与上一个列重叠。
排序后，区间列为
[[x1, y1], [x1, y2], ..., [x1, ym], [x2, z1], [x2, z2], ..., [x2, zn], [x3, w1],...]；其中x1<x2<x3<…
讨论第一个以x2为左端点的区间[x2,z1]：
– 如果它与前面的[x1, ym]重叠，则后面的以x2为左端的区间列也与第一个[x2, z1]重叠，这构成连续的重叠区间；
-如果不与前面的[x1, ym]重叠，则由于x1<ym<x2且x2<z1,z2,…，后面的以x2为左端的区间列也肯定不与[x1, ym]重叠，从而整个 以x2为左端的区间列 都不与整个 以x1为左端的区间列重叠。
于是，用变量merged保存合并后的元素，让其最后一个元素（区间）一个个合并上述区间列的元素：
– 将第一个区间加入merged。
– 迭代这个升序区间列，若当前元素可以与merged的最后一个元素合并，则将这最后一个元素替换成合并后的元素；不然，则直接插入merged。
代码：
class Solution:
def merge(self, intervals: list[List[int]]) -> list[list[int]]:
if len(intervals) == 1: return intervals
intervals.sort(key = lambda x: x[0]) # 这个lambda函数表示传入的迭代区间将输出区间的第一个元素（左端点）
merged = [intervals[0]]
for interval in intervals[1:]:
if merged[-1][1] < interval[0]: merged.append(interval) # 如果不重叠，则直接加入当前区间
else:
# 只要更改右端点就可以了。因为merged最后一元素的左端点，一定小于等于当前元素的左端点
merged[-1][1] = max(interval[1], merged[-1][1])
return merged
其复杂度为$O(n \mathrm{log}n)$：排序花费$O(n \mathrm{log}n)$，合并花费$O(n)$。
缺失的第一个正数（First Missing Positive）
题目要求：给你一个未排序的整数数组nums，请你找出其中没有出现的最小的正整数。要求时间复杂度$O(n)$、空间复杂度$O(1)$。
示例：
输入：nums = [1,2,0]
输出：3
解释：范围 [1,2] 中的数字都在数组中。
输入：nums = [3,4,-1,1]
输出：2
解释：1 在数组中，但 2 没有。
思路：排序先pass掉；想到之前的根堆结构，claude了一番后发现可以用$O(\mathrm{log}n)$的时间构造根堆；但要是缺失的正数在所有正数的中间位置，那么每寻找一次正数又得耗掉$O(n)$，结果平均复杂度直接变平方……
题解：首先我们可以注意到？，对于长度为n的数组，缺失的正整数一定在[1,n+1]之间。
– 如果这个数组正好放满1~n的所有数，那么缺失的最小正整数就是n+1。
– 不然，[1,n]中一定至少缺失一个，把它找出来。
先给出空间复杂度$O(n)$的：构造哈希表（字典），记录正数1~n是否存在。遍历一遍数组用字典记录好后，在字典中寻找第一个不存在的正数；若都存在，则缺失的最小正数为n+1。
如何改进空间复杂度？注意到我怎么就注意不到啊传入的数组本身也能当哈希用。具体操作如下：
– 把数组中所有的非正数都替换为n+1。毕竟找这个整数的过程中，非正数无论变成什么样都不影响判断；且缺失的最小整数最大也就是n+1
– 此时数组的每个元素全正，且元素在[1,n]中的不变。接下来就不要关心数组的值了，只看数组下标。遍历数组时，把当前元素nums[i]当作下标，检测第nums[i]-1个位置的元素是否为负；若不是，则把它标记为负数（乘以-1），记作这个整数已存在。
– 标记负数时可能会将待判断的位置变负。我们的判断条件应带上绝对值：if 1 <= abs(nums[i]) <= n and nums[abs(nums[i])-1] > 0:
最后看看哪个位置是正的，如果位置i的元素为正，那就说明i+1是缺失的最小正数；否则，若所有的数都负，那就说明[1,n]中的每个正数都能在数组中找到，于是缺失的最小正数为n+1。
代码：
class Solution:
def firstMissingPositive(self, nums: list[int]) -> int:
posnums = {}
n = len(nums)
for i in range(1,n+1):
posnums[i] = False # 正数i是否在数组中存在？
for num in nums:
if 0 < num < n+1: posnums[num] = True
for positive in posnums.keys():
if posnums[positive] == False: return positive
return n+1
def firstMissingPositive2(self, nums: list[int]) -> int:
n = len(nums)
for i in range(n):
if nums[i] <= 0: nums[i] = n+1 # 把数组里的非正数全改成n+1
for i in range(n):
if 1 <= abs(nums[i]) <= n and nums[abs(nums[i])-1] > 0: # 如果当前数字是1~n中的一个，且对应的位置未被标记（用负号标记它）
nums[abs(nums[i])-1] *= -1 # 用负号标记
for i in range(n):
if nums[i] > 0: return i+1
return n+1