2. 两数相加
解题思路
竖式相加。
要注意的点：
1.链表不等长，因此要在某个链表节点不够的情况下补0。
2.有可能连续进位，使得最后的数字超出最长的链表节点数，所以要判断进位变量的最后状态，若还有值，要新建一个节点。
步骤
1.初始化哑结点，指针节点指向哑结点
2.初始化进位和当前位的值
3.建立循环，要求遍历完全部链表
4.循环体内定义某个链表长度不足时补0
5.计算当前位和进位的值
6.将当前位新建为节点，添加到结果链表后。移动指针节点
7.移动链表节点
8.检查是否进位非0，还有值就新建节点添加进尾部
9.返回头节点。哑结点的下一个节点
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
# 哑结点
dummy = ListNode(0)
cur = dummy
carry = 0 # 进位初始化为0
_sum = 0 # 当前位初始化为0
# 考虑不等长情况,补0
while l1 or l2:
if not l1:
l1 = ListNode(0)
if not l2:
l2 = ListNode(0)
# 求和
_sum = l1.val + l2.val + carry
# 个位
now = _sum % 10
# 检查十位
carry = _sum // 10
# 将个位写入新节点，加入结果链表
cur.next = ListNode(now)
cur = cur.next # 不要忘记移动指针
# 移动
l1 = l1.next
l2 = l2.next
# 如果十位数连续多进位，导致最后只有进位的，就新建一个节点是它，续在末尾
# 也就是该变量最后非0
if carry:
cur.next = ListNode(carry)
return dummy.next
155. 最小栈
既要获得栈顶元素，又要立即获得栈的最小元素。
设定一个主栈还有一个辅助栈，辅助栈只存储当前最小元素。
实现思路：
-
使用两个栈：
- 主栈：用于存储所有元素，实现正常的栈操作。
- 辅助栈：用于存储每个阶段的最小值。
-
操作解释：
- push(x)：将元素 x 压入主栈。同时，将当前最小值压入辅助栈。这个当前最小值是 x 和辅助栈顶元素的较小者。
- pop()：从主栈中弹出顶部元素。同时，从辅助栈中也弹出顶部元素（保持两个栈的同步）。
- top()：返回主栈的顶部元素，不从栈中移除。
- getMin()：返回辅助栈的顶部元素，即当前栈中的最小值。
class MinStack:
def __init__(self):
# 主栈
self.stack = []
# 最小栈
self.min_stack = []
def push(self, val: int) -> None:
# 同时入栈
# 主栈直接入
self.stack.append(val)
# 最小栈检测是否是有值且最小的，保证每次都是最小的在最小栈最后
if not self.min_stack or val <= self.min_stack[-1]:
self.min_stack.append(val)
def pop(self) -> None:
# 栈顶出栈，删除最后一个元素
item = self.stack.pop()
# 如果弹出的是最小值，那最小栈也要弹出对应元素
if item == self.min_stack[-1]:
self.min_stack.pop()
def top(self) -> int:
# 获取栈顶部的元素
item = self.stack[-1]
return item
def getMin(self) -> int:
# 获取栈中的最小元素
item = self.min_stack[-1]
return item
# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()
20. 有效的括号
解题思路：
正确的括号组合应该是开放括号在前，同时开放括号所对应的闭合括号的位置是和本身的位置对称的。
也就是如果开放括号后再也没有开放括号了，那么下一个就必须是所对应的闭合括号，这样才能对应。
根据以上分析，可以使用栈结构处理，栈是先进后出的。
假设我们有’{([])}‘，那么遍历字符串，对开放括号入栈，得到[’{', ‘(’, ‘[’ ]，如果说下一个字符不是[所对应的]，那么就说明位置错乱，直接返回false；如果遍历完后还是空栈，说明也没有多余的括号，是正确的，返回True。
在上述操作中，首先需要一个字典存储开放和闭合括号的映射关系；其次，每次都可能尝试弹出栈顶元素，要是第一次就是个闭合括号，那程序不就报错了（未入栈，栈为空），因此还要添加一个默认值，防止空栈访问。
步骤
1.初始化一个字典和栈，字典包含开放：闭合，加上占位符号。栈加上占位字符。
2.遍历字符串，遇到开放括号，入栈。
3.否则，也就是遇见闭合括号，访问栈顶元素，检查是否是其对应的开放括号，如果不是，就说明位置错误，直接返回false。
4.遍历完字符串，检查栈中元素只有最开始的占位字符，如果是，说明已经全部消消乐掉了，返回True；否则，说明还有多余的括号，返回false。
class Solution:
def isValid(self, s: str) -> bool:
# 括号开放闭合字典
bracket_map = {
'(':')', '{':'}', '[':']', '#':'#'
}
# 栈
stack = ["#"]
# 遍历字符串
for i in s:
# 如果是开放符号，入栈
if i in bracket_map:
stack.append(i)
# 如果当前字符不是刚入栈的开放括号对应的闭合括号，说明位置错乱
elif bracket_map[stack.pop()] != i:
return False
# 遍历完成后，所有括号都应该消除，只剩一个占位字符
return len(stack) == 1
227. 基本计算器 II
解题思路
利用栈，维护一个全都是待加元素的栈。
在解析出数字的时候不能直接入栈，而是要看前一个运算符决定。
每个数字加入栈的最终形式，是由前一个运算符决定的，比如3，其前一个运算符就是+，直接入栈；而*3，其前一个运算符是*，那就要和栈顶元素相乘再重新入栈。
步骤
1.初始化栈，符号变量为+，数字为0
2.需要解析出每一个数字，因此遍历字符串，检查是否为数字，是数字则将字符转为数字，并要考虑可能有十位百位数，因此每次遍历都要检查当前数字*10.
3.如果字符为运算符，说明当前数字已经确定了，根据当前数字的前面的运算符计算入栈的结果：加减简单，乘的话是要先弹出栈顶元素，当前数字和栈顶元素相乘，乘积入栈；除法，因为 Python 的 // 运算符在被除数为负数时会向下取整到更小的整数，而通常的数学操作是向零取整，所以要考虑栈顶元素的正负，是负数时需要用最原始的解法。
4.当前字符为字符串，在将确定的数字入栈后，更新运算符变量和数字变量。
5.返回栈内所有元素的和。
class Solution:
def calculate(self, s: str) -> int:
# 初始化栈，符号变量，当前数字
stack = []
sign = '+' # 第一个为正
num = 0
s += '+' # 给字符串末尾加一个符号，防止最后一个数字加不上(标识最后一个数字的结束)
# 遍历字符串
for i in s:
# 如果是数字，就构造数字
if i.isdigit():
# 乘10是将已解析的数字往左移动一位，使得123这样的字符串能被正确识别，而不是变成6
# 因为我们每次读到一个新的数字字符时，都需要将之前的数字值“扩大10倍”再加上新的数字。
num = 10 * num + int(i)
# 如果是运算符
elif i in '+-*/':
# 如果是前面是加，那就直接把当前数字入栈
if sign == '+':
stack.append(num)
# 如果前面是减，那就将相反数入栈
elif sign == '-':
stack.append(-num)
# 如果前面是乘，就弹出栈顶的元素相乘
elif sign == '*':
stack.append(stack.pop() * num)
# 如果前面是除，那就要保留整数半部分，、
# 但是因为Python的//在处理负数时向下取整，但是正常是向零取整，所以要先正常除，然后转整数
else:
temp = stack.pop()
if temp < 0:
stack.append(int(temp/num))
else:
stack.append(temp//num)
# 遍历到运算符，更新运算符变量
sign = i
# 当前无数字，重置数字变量
num = 0
return sum(stack)
232. 用栈实现队列
解题思路
使用两个栈，逆向存储。
入队操作就直接入主栈；
移除队首元素，就先将主栈元素依次弹出，入辅助栈，这样辅助栈的栈顶元素就是队首元素，弹出即可，记得返回；
获取队首元素，同上，但是不能弹出，不是移除；
检查是否为空，检查两个栈是否都为空。
class MyQueue:
def __init__(self):
# 主栈
self.in_stack = []
# 辅助栈
self.out_stack = []
def push(self, x: int) -> None:
# 入栈
self.in_stack.append(x)
def pop(self) -> int:
# 出栈，检查辅助栈是否有值，有值就弹出栈顶元素
# 没有，就将主栈元素依次弹出到辅助栈
if not self.out_stack:
while self.in_stack:
self.out_stack.append(self.in_stack.pop())
return self.out_stack.pop()
# 获取队首元素
def peek(self) -> int:
if not self.out_stack:
while self.in_stack:
self.out_stack.append(self.in_stack.pop())
# 不删除元素
return self.out_stack[-1]
# 检查是否队列为空
def empty(self) -> bool:
return not self.in_stack and not self.out_stack
# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()
394. 字符串解码
解题思路
使用栈。类似于计算器二，对于数字都要考虑是多位的情况。
设置当前字符串和当前数字，用于遍历时入栈。
当遍历到数字时要解析数字。如果是左括号，就可以确定解析的数字了，还有当前的字符编码开始了。将其入栈。
如果是字符，说明还在增加字符编码，累加到当前字符串。
如果是右括号，说明字符编码已确定，需要将数字和字符编码结合，加到前一个字符串后面。
最后返回字符串。
步骤
您的代码实现基本上是正确的，对于394题“字符串解码”的解决方案很好地处理了基本情况，包括数字的读取、字符串的累积和括号内字符串的重复。我会先提供一个简单的算法步骤说明，然后对代码进行逐行检查和说明。
算法步骤
初始化数据结构：
- 使用一个栈来存储先前的状态。
- 使用两个变量
cur_num和cur_str来分别存储当前解析的重复次数和当前解析的字符串。遍历输入字符串：
- 如果当前字符是数字，将其转换为整数并更新
cur_num。- 如果当前字符是
[，表示一个新的重复序列的开始，将cur_num和cur_str压入栈中，然后重置这两个变量。- 如果当前字符是
]，表示一个重复序列的结束，从栈中弹出之前的字符串和重复次数，根据这个重复次数将当前字符串重复拼接，然后与之前的字符串连接。- 如果当前字符是字母，将其添加到
cur_str中。返回最终解析的字符串：
- 遍历完成后，
cur_str包含了整个解析后的字符串。
class Solution:
def decodeString(self, s: str) -> str:
stack = [] # 用于保存之前的字符串状态和重复次数
cur_num = 0 # 当前解析的数字，即重复次数
cur_str = '' # 当前解析的字符串
for i in s:
if i.isdigit():
cur_num = 10 * cur_num + int(i) # 构建整数，处理多位数的情况
elif i == '[':
stack.append(cur_num) # 将当前重复次数压入栈
stack.append(cur_str) # 将当前字符串压入栈
cur_num = 0 # 重置重复次数
cur_str = '' # 重置当前字符串
elif i == ']':
pre_str = stack.pop() # 弹出上一个字符串状态
pre_k = stack.pop() # 弹出上一个重复次数
cur_str = pre_str + (cur_str * pre_k) # 根据重复次数构造字符串，并与之前的字符串连接
else:
cur_str += i # 累加非括号内的字符到当前字符串
return cur_str # 返回解析后的字符串
32. 最长有效括号
解题思路
栈先进后出，适合括号是否有效问题。
遍历字符串，只入栈左括号时的索引；否则，弹出栈顶元素，计算当前索引和当前栈顶元素的差值。这样不断更新最长长度。消消乐
步骤
1.初始化：创建一个栈，用于保存括号的索引，并先压入 -1 作为基准点，方便计算长度。
遍历字符串：
2.如果遇到 (，将其索引压入栈中。
3.如果遇到 )：弹出栈顶元素。然后
- 如果栈为空，将当前索引压入栈（这成为新的基准点）。
- 如果栈不为空，计算当前有效括号的长度，即 当前索引 - 栈顶元素索引，更新最大长度。
4.返回最大长度。
class Solution:
def longestValidParentheses(self, s: str) -> int:
# 初始化栈，使用-1作为初始基准点，这样对于'()'也能正确计算出是2
stack = [-1]
max_len = 0 # 最大长度
# 遍历字符串
for i in range(len(s)):
# 如果是左括号索引，就入栈
if s[i] == '(':
stack.append(i)
# 如果是右括号，弹出栈顶的左括号索引
else:
stack.pop()
# 如果栈为空，说明一个连续的有效子串已经被消耗完。将当前索引入栈作为新的基准
if not stack:
stack.append(i)
# 更新最长长度
# 此时消掉了栈顶元素索引和当前索引，所以最长长度为目前栈顶元素和当前索引之差
max_len = max(max_len, i - stack[-1])
return max_len
42. 接雨水
著名hard题，我是不做的😇
双指针法
问题42 “接雨水” 要求计算在一个由整数表示的条形图中，可以存多少单位的雨水。这是一个经典的问题，可以通过几种方法解决，包括使用栈、动态规划或双指针。
解题思路：双指针法
双指针法是解决这个问题的一种高效方式。基本思想是用两个指针从两头开始遍历数组，使用两个变量来记录左右两边的最大高度，从而计算每个位置上能接的雨水量。
步骤：
初始化：
left指针开始于数组的第一个位置。right指针开始于数组的最后一个位置。left_max和right_max分别记录遍历过程中遇到的左侧和右侧的最大高度。water初始化为0，用于累计总的接水量。遍历数组：
- 使用
while循环，当left小于right时继续遍历。- 比较
height[left]和height[right]：
- 如果
height[left]小于或等于height[right]，则处理左边的部分：
- 更新
left_max。- 如果
left_max大于height[left]，累加差值到water。- 移动
left指针向右。- 否则，处理右边的部分：
- 更新
right_max。- 如果
right_max大于height[right]，累加差值到water。- 移动
right指针向左。返回结果：
- 循环结束后，
water中存储的就是可以接的雨水总量。
class Solution:
def trap(self, height):
# 如果没有柱子或者小于3个，那就无法存贮水
if not height or len(height) < 3:
return 0
# 初始化左右指针
left, right = 0, len(height) - 1
# 初始化左右边遇到的最大值
left_max, right_max = height[left], height[right]
# 接水量
water_trapped = 0
# 当双指针不相遇时
while left < right:
# 当左边柱子比右边低
if height[left] < height[right]:
# 如果当前柱子比最高还高，更新左边的最高值
if height[left] >= left_max:
left_max = height[left]
# 否则，认定为有积水，积水量等于最高值减去当前的柱子高度
else:
water_trapped += left_max - height[left]
# 左边柱子低，往右移动
left += 1
# 当右边柱子比左边低
else:
# 如果当前柱子比最高还高，更新右边的最高值
if height[right] >= right_max:
right_max = height[right]
# 否则，认定为有积水，积水量等于最高值减去当前的柱子高度
else:
water_trapped += right_max - height[right]
# 右边柱子低，往左移动
right -= 1
return water_trapped
解释
- 此方法的核心在于，通过维护两个最大高度（从左和从右）来确定当前位置能接的雨水。
- 当
height[left]较小时，水的高度由左侧最高的条形块决定（因为右边至少有一个条形块更高），反之亦然。
这种双指针方法的时间复杂度为 (O(n))，空间复杂度为 (O(1))，因为它只需要常数空间来存储指针和高度变量。
栈
使用栈来解决接雨水问题也是一个非常有效的方法。通过栈，我们可以保持一个减少的高度序列，这样每次我们碰到一个比栈顶更高的条形块时，就可以计算接到的雨水量。
解题思路：使用栈
步骤：
初始化：
- 创建一个空栈，用来存储条形块的索引。
- 初始化
water为 0，用于累计总的接水量。遍历数组：
- 对于每个条形块，执行以下操作：
- 当栈不为空且当前条形块的高度大于栈顶条形块的高度时，执行循环：
- 弹出栈顶元素（索引），记为
top。- 如果栈变为空，跳出循环（没有左边界）。
- 查找新的栈顶元素，这将是
top的左边界。- 计算当前水的宽度和高度：
- 宽度为
current index - stack top index - 1- 高度为
min(height[current index], height[stack top index]) - height[top]- 计算接的水量并加到
water上。- 将当前条形块的索引压入栈中。
返回结果：
- 遍历结束后，
water中存储的就是可以接的雨水总量。
class Solution:
def trap(self, height):
# 初始化一个空栈来保存条形块的索引
stack = []
# 初始化水量计数为0
water = 0
# 从第一个条形块开始遍历
current = 0
# 遍历所有的条形块
while current < len(height):
# 当栈不为空且当前条形块高度大于栈顶条形块高度时
while stack and height[current] > height[stack[-1]]:
# 弹出栈顶元素，这是凹形区域的底部
top = stack.pop()
# 如果栈为空，说明没有左边界，跳出循环
if not stack:
break
# 计算当前凹形区域的宽度
distance = current - stack[-1] - 1
# 找到边界高度的最小值，并减去凹底的高度，得到水的高度
bounded_height = min(height[current], height[stack[-1]]) - height[top]
# 根据宽度和水的高度计算当前凹形区域的水量，并加到总水量中
water += distance * bounded_height
# 将当前条形块索引压入栈中，表示可能的新的凹形区域的右边界
stack.append(current)
# 移动到下一个条形块
current += 1
# 返回计算的总水量
return water
解释
- 此方法利用栈来追踪可能存水的位置。
- 当遇到一个条形块高于栈顶条形块时，可以确定一个凹形区域（即接水的区域）。通过计算这个凹形区域的宽度和界限高度来确定其可以接的水量。
- 重复这一过程直到遍历完整个数组。
使用栈的方法在处理复杂的嵌套结构和计算界限时非常直观和有效。此方法的时间复杂度为 (O(n))，因为每个条形块最多被压入和弹出栈一次。空间复杂度也为 (O(n))，最坏情况下栈可能需要存储所有条形块的索引。
225. 用队列实现栈
解题思路
设置主队列和辅助队列，每次入栈先进入辅助队列，然后将主队列的全部元素依次入辅助队列，这样辅助队列的首个元素就是栈顶元素。再交叉引用，让主队列得到新的栈顺序
两个队列实现栈的操作步骤：
初始化
mainQueue用于存储栈内元素。tempQueue用于push操作中的元素顺序调整。push(x) 操作
- 将新元素
x入队到tempQueue。- 将
mainQueue中的所有元素依次出队，并入队到tempQueue。- 交换
mainQueue和tempQueue的引用，使mainQueue包含新的元素序列，tempQueue为空。pop() 操作
- 直接从
mainQueue出队一个元素（即栈顶元素）。top() 操作
- 返回
mainQueue的队首元素（即栈顶元素）。empty() 操作
- 检查
mainQueue是否为空。
Python 示例代码
from collections import deque
class MyStack:
def __init__(self):
"""Initialize your data structure here."""
self.mainQueue = deque()
self.tempQueue = deque()
def push(self, x: int):
"""Push element x onto stack."""
# 先将元素入队到 tempQueue
self.tempQueue.append(x)
# 将 mainQueue 中的所有元素移到 tempQueue
while self.mainQueue:
self.tempQueue.append(self.mainQueue.popleft())
# 交换两个队列的引用，使 mainQueue 包含新的栈顺序
self.mainQueue, self.tempQueue = self.tempQueue, self.mainQueue
def pop(self):
"""Removes the element on top of the stack and returns that element."""
return self.mainQueue.popleft()
def top(self):
"""Get the top element."""
return self.mainQueue[0]
def empty(self):
"""Returns whether the stack is empty."""
return not self.mainQueue
# Usage
stack = MyStack()
stack.push(1)
stack.push(2)
print(stack.top()) # returns 2
print(stack.pop()) # returns 2
print(stack.empty()) # returns False
这种实现方法虽然在每次 push 操作时需要移动所有元素（时间复杂度 O(n)），但它确保了 pop、top 和 empty 操作都是 O(1) 的时间复杂度。这样，栈的后进先出行为通过队列被成功模拟出来了。
1. 两数之和
解题思路1
双重循环，第二层循环应该从i+1开始，避免i==j的情况
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
# 双重循环
# 遍历所有
for i in range(len(nums)):
# 遍历从i+1到最后，避免i==j的情况
for j in range(i+1, len(nums)):
# 发现有符号条件的，返回索引
if nums[i] + nums[j] == target:
return [i,j]
解题思路2
哈希表。
遍历数组，计算每个数字和目标值的差值，如果插值存在，则返回。否则加入当前数字。
key: 数字，vlaue:索引
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
# 哈希表
_dict = {}
# 遍历，记录索引
for i,num in enumerate(nums):
# 计算当前数和目标值的差值
temp = target - num
# 如果和差值相同的数字在哈希表内，就说明找到了两个数，返回对应下标
if temp in _dict:
return [_dict[temp], i]
# 否则，将当前数作为键，当前索引作为值加入哈希表
_dict[num] = i
15. 三数之和
解题思路
排序加双指针。
先对数组排序，遍历数组，每次遍历都要跳过重复数字，然后初始化左右指针，在左右区间内尝试找到三个数字满足条件。
如果小于0，移动左指针；大于，移动右指针；等于，就找到了符号要求的三个数字，加入到结果列表。
找到一组结果，不代表这个区间内没有了，因此还要跳过左右指针的重复元素，避免找到相同的结果。最后移动左右指针到新的元素。
- 排序：首先对数组进行排序。排序有助于后续操作，特别是在跳过重复元素时。
- 使用固定指针和双指针：
- 固定一个数
nums[i]，然后使用两个指针，一个指向i+1（left），另一个指向数组的最后一个元素（right）。- 移动
left和right指针来找到三元组，使得nums[i] + nums[left] + nums[right] == 0。- 处理重复元素：
- 在遍历和移动指针时，要注意跳过重复的元素以避免重复的三元组。
- 时间复杂度：排序操作为 (O(n \log n))，双指针扫描为 (O(n^2))，整体复杂度为 (O(n^2))。
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
# 排序
nums.sort()
res = [] # 结果列表
# 遍历数组
for i in range(len(nums)-2):
# 经过排序后，如果当前数字大于0，那剩下加上肯定也大于0
if nums[i] > 0:
break
# 跳过重复元素
if nums[i] == nums[i-1] and i > 0:
continue
# 设置左右指针，从不重复的开始
left, right = i+1, len(nums)-1
# 开始循环
while left < right:
total = nums[i] + nums[left] + nums[right]
if total < 0: # 如果总和小于0，说明负数太大
left += 1
elif total > 0: # 正数太大
right -= 1
else: # 找到了目标，加入到结果列表
res.append([nums[i], nums[left], nums[right]])
# 然后跳过重复元素
while left < right and nums[left] == nums[left+1]:
left += 1
while left < right and nums[right] == nums[right-1]:
right -= 1
# 移动指针
left += 1
right -= 1
return res
说明
- 排序：排序是为了方便处理重复元素和简化三数之和的查找。
- 双指针移动：通过比较三数之和与零的关系来决定指针的移动方向。
- 去重：在找到一个有效的三元组后，需要跳过所有重复的元素，以确保结果的唯一性。
41. 缺失的第一个正数
解题思路
原地哈希。因为要求不使用额外空间，所以可以将数字和其索引作为哈希表的键和值。
尝试将所有的数字都放在对应的索引上，如果说有不对应的，那就是缺失。
第一次遍历，将乱序数组进行原地哈希；第二次遍历，找到缺失值。
步骤
1.第一次遍历：检查每个数字是否在1-n（n为数组长度）之间，索引对应的位置是否是正确的数字。如果不是，则要进行交换，使其回到对应的索引为止。
nums[nums[i]-1] != nums[i]
对于数字nums[i]，应该放在数组的nums[i]-1位置上，如果该位置上的数字不等于它，说明位置不对。
2.第二次遍历：针对原地哈希后的数组，检测是否有不满足原地哈希的索引，返回其+1，也就是缺失的第一个值
3.如果以上没有返回，那就说明是满足原地哈希的。返回数组后面的第一个整数。
class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
# 原地哈希，数字1:索引0
n = len(nums)
# 遍历数组
for i in range(n):
# 当数字在1到n之间，并且没有在正确的位置上，数字和索引之间差1
while 1 <= nums[i] <= n and nums[nums[i]-1] != nums[i]:
# 就要将 nums[i] 交换到它应该去的位置，也就是nums[nums[i]-1]
nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
# 原地哈希结束后，如果有不满足原地哈希条件的，就返回其值（索引+1）
for i in range(n):
if nums[i]-1 != i:
return i + 1
# 如果数组所有元素都没有不符合要求的，那结果就是后面的正整数缺失
return n + 1
128. 最长连续序列
解题思路
利用哈希集合。遍历哈希集合，每次尝试找到一个新的子序列起点（当前值-1不在哈希集合），然后扩展它（当前值+1在集合），找到完整的子序列后，更新结果。
步骤
1.初始化哈希集合和结果变量。
2.遍历哈希集合，检查当前元素是否为一个新的子序列起点
3.如果是，就将子序列长度初始化为1，子序列起点设为当前元素；然后以子序列起点，找是否有下一个元素，有的话就将子序列起点更新为它，并且子序列长度加1.最后找不到下一个元素了，说明子序列到此为止，更新结果。
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
# 集合
nums = set(nums)
# 最大长度
res = 0
for i in nums:
# 只有其前一个数字不在集合中，才算一个新的连续子序列的开始
if (i-1) not in nums:
cur_num = i # 当前数字作为子序列的起点
cur_res = 1 # 当前子序列的长度初始化为1
# 尝试从子序列起点构建连续序列，检查后一个数是否存在于集合
while (cur_num+1) in nums:
cur_num += 1 # 子序列起点更新
cur_res += 1 # 子序列长度更新
# 在得到一个完整的子序列后，更新最长长度
res = max(res, cur_res)
# 返回结果
return res
