LeetCode Hot 100 思路速览#

每题覆盖核心思路 + 关键步骤，看完即可还原解题流程，适合复习扫描。

哈希#

1. 两数之和#

题目描述： 给定一个整数数组nums和一个整数目标值target，请你在该数组中找出和为目标值target的那两个整数，并返回它们的数组下标。

思路：哈希表一次遍历 遍历数组，对每个 nums[i]，先查哈希表中是否存在 target - nums[i]：

存在 → 返回 [哈希表中存的下标, i]
不存在 → 将 nums[i] → i 存入哈希表

时间 O(n)，空间 O(n)。

49. 字母异位词分组#

题目描述： 给定一个字符串数组 strs，请将所有字母异位词放到同一个分组中。字母异位词指由相同字母重排得到的字符串。

思路：排序字符串作 key

遍历每个字符串，将其排序后的结果作为 key
以 key 为分组，原字符串归入对应 value 列表
返回所有 value 列表

时间 O(n·k·log k)，k 为字符串平均长度。

128. 最长连续序列#

题目描述： 给定一个未排序的整数数组 nums，请找出数字连续的最长序列长度。这里的“连续”只要求数值连续，不要求这些元素在原数组中的位置连续。

思路：哈希集合 + 只从序列起点计数

所有数加入哈希集合
遍历，只对 num-1 不在集合中的数（即序列起点）向右扩展：num, num+1, num+2 ... 直到不连续
更新全局最大长度

时间 O(n)（每个数最多被访问两次）。

双指针#

283. 移动零#

题目描述： 给定一个数组 nums，请将所有 0 移动到数组末尾，同时保持非零元素的相对顺序不变。要求必须在原数组上原地操作，不能额外创建同规模数组。

思路：快慢双指针，慢指针指向下一个待覆盖位

slow 指向下一个应放非零元素的位置，初始为 0
fast 遍历数组，遇到非零元素就将其放到 slow 位置，slow++
遍历结束后，slow 之后的位置全部填 0

时间 O(n)，空间 O(1)。

11. 盛最多水的容器#

题目描述： 给定一个长度为n的整数数组height，有n条垂线，第i条线的两个端点是(i, 0)和(i, height[i])。找出其中的两条线，使得它们与x轴共同构成的容器可以容纳最多的水。

思路：左右双指针，每次移动较短一侧

left=0, right=n-1
每次计算当前面积 = min(h[left], h[right]) × (right - left)，更新最大值
移动较短的一侧（移动较长侧不可能增大面积）
直到 left >= right

时间 O(n)，空间 O(1)。

15. 三数之和#

题目描述： 给定一个整数数组 nums，请找出所有和为 0 且不重复的三元组。返回的三元组中，元素顺序和结果顺序都不作要求，但三元组本身不能重复。

思路：排序 + 固定一个 + 双指针

排序数组
固定 i（从 0 到 n-3），令 left=i+1, right=n-1
三数之和 > 0 → right--；< 0 → left++；= 0 → 记录，同时跳过重复的 left 和 right
外层循环也跳过重复的 i（nums[i] == nums[i-1] 时 continue）

时间 O(n²)，空间 O(1)。

42. 接雨水#

题目描述： 给定 n 个非负整数表示柱状图中每个宽度为 1 的柱子高度，计算下雨之后这组柱子一共能接住多少雨水。

思路：左右双指针，维护两侧历史最大高度

left=0, right=n-1，maxLeft=0, maxRight=0
每次处理较矮的一侧：
- h[left] < h[right]：更新 maxLeft = max(maxLeft, h[left])，当前可接水 = maxLeft - h[left]，left++
- 否则：更新 maxRight，当前可接水 = maxRight - h[right]，right--
累加可接水量

时间 O(n)，空间 O(1)。

滑动窗口#

3. 无重复字符的最长子串#

题目描述： 给定一个字符串 s，请找出其中不含重复字符的最长子串长度。

思路：哈希集合维护窗口，左指针按需右移

left=0，哈希集合记录窗口内字符
right 右移：若 s[right] 已在集合中，循环移除 s[left] 并 left++ 直到无重复
将 s[right] 加入集合，更新最大窗口长度 right - left + 1

时间 O(n)，空间 O(字符集大小)。

438. 找到字符串中所有字母异位词#

题目描述： 给定两个字符串 s 和 p，请找出 s 中所有 p 的字母异位词子串，并返回这些子串的起始下标。答案顺序不限。

思路：固定长度窗口 + 字符频次比较

统计目标串 p 的字符频次 need[26]
用大小为 p.length 的窗口在 s 上滑动，维护窗口频次 window[26]
每次移动时：新加入右侧字符频次 +1，移出左侧字符频次 -1
每次判断 window == need，相等则记录 left 为起始索引

时间 O(n)，空间 O(1)（字符集固定 26）。

560. 和为K的子数组#

题目描述： 给你一个整数数组 nums 和一个整数 k，请统计并返回数组中和为 k 的连续子数组个数。

思路：前缀和 + 哈希表（不能用滑动窗口，因为有负数）

preSum=0，哈希表存 {前缀和 → 出现次数}，初始化 {0: 1}（空前缀）
遍历数组，preSum += nums[i]
查哈希表中 preSum - k 出现的次数，累加到答案（表示存在以当前位置结尾、和为 k 的子数组）
将 preSum 存入哈希表

时间 O(n)，空间 O(n)。

239. 滑动窗口最大值#

题目描述： 给你一个整数数组 nums ，有一个大小为 k 的滑动窗口从数组最左侧移动到最右侧。窗口每次只向右移动一位。请返回每次窗口移动后窗口中的最大值。

思路：单调递减双端队列（存下标）

维护双端队列，队首始终是当前窗口最大值的下标
每次右移 right：
- 从队尾依次移除所有值 ≤ nums[right] 的下标（它们永远不会是最大值）
- 将 right 加入队尾
- 若队首下标已滑出窗口（deque[0] < right - k + 1），移除队首
当 right >= k-1 时，队首对应的值即为当前窗口最大值

时间 O(n)，空间 O(k)。

76. 最小覆盖子串#

题目描述： 给你一个字符串 S 和一个字符串 T，请在 S 中找出包含 T 所有字符的最小子串。

思路：可变滑动窗口 + 满足条件时收缩

统计 t 中字符频次到 need，missing 记录还差多少个字符（初始 = t.length）
right 右扩：若加入字符能补缺（need[ch]-- > 0），missing--
missing == 0 时，循环用 left 收缩：移出字符时若 ++need[ch] > 0 则 missing++ 停止收缩，每次收缩前更新最小窗口
重复直到 right 到末尾

时间 O(n)，空间 O(字符集)。

普通数组#

53. 最大子数组和#

题目描述： 给你一个整数数组 nums，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

思路：Kadane 算法，动态规划

curSum = nums[0]，maxSum = nums[0]
从第 2 个元素开始：curSum = max(nums[i], curSum + nums[i])（要么重新开始，要么继续累加）
maxSum = max(maxSum, curSum)

时间 O(n)，空间 O(1)。

56. 合并区间#

题目描述： 给出一个区间的集合，请合并所有重叠的区间。

思路：按起始位置排序后线性扫描合并

按 start 升序排序
初始化结果集，放入第一个区间
遍历后续区间：若当前区间的 start ≤ 结果集末尾区间的 end → 合并（更新末尾 end 为两者较大值）；否则直接加入结果集

时间 O(n log n)，空间 O(n)。

189. 轮转数组#

题目描述： 给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

思路：三次反转法，O(1) 额外空间

k = k % n（避免超出长度）
反转整个数组
反转前 k 个元素
反转后 n-k 个元素

例：[1,2,3,4,5], k=2 → 反转全部 [5,4,3,2,1] → 反转前2 [4,5,3,2,1] → 反转后3 [4,5,1,2,3]。

238. 除自身以外数组的乘积#

题目描述： 给你一个整数数组 nums，返回一个新数组 answer，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。题目要求不能使用除法。

思路：两次遍历，前缀积 × 后缀积

第一遍从左到右，res[i] = i 左侧所有数的乘积（res[0]=1 起始）
第二遍从右到左，用变量 right 维护右侧乘积（初始为 1），res[i] *= right，然后 right *= nums[i]

时间 O(n)，空间 O(1)（输出数组不计）。

41. 缺失的第一个正数#

题目描述： 给你一个未排序的整数数组 nums，请你找出其中没有出现的最小的正整数。请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

思路：原地哈希，将值 x 放到下标 x-1 处

遍历数组：若 nums[i] 在 [1, n] 范围内且 nums[nums[i]-1] != nums[i]，则将其与 nums[nums[i]-1] 交换，直到无法交换
再次遍历：找第一个 nums[i] != i+1 的位置，返回 i+1
若全部对应，返回 n+1

时间 O(n)，空间 O(1)。

矩阵#

73. 矩阵置零#

题目描述： 给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。

思路：用首行首列作为标记，O(1) 额外空间

先判断第 0 行和第 0 列自身是否含 0（用两个 bool 变量记录）
遍历矩阵（从 [1][1] 开始），若 matrix[i][j]==0，则将 matrix[i][0] 和 matrix[0][j] 置为 0
根据首行首列的标记，将对应行/列全部置 0
最后根据步骤 1 的 bool 变量处理第 0 行和第 0 列

54. 螺旋矩阵#

题目描述： 给你一个 m x n 的矩阵，请按照顺时针螺旋顺序，返回矩阵中的所有元素。

思路：四边界模拟法

维护 top, bottom, left, right 四个边界
循环按顺序遍历：向右（top 行）→ 向下（right 列）→ 向左（bottom 行，需 top<bottom）→ 向上（left 列，需 left<right）
每个方向遍历后收缩对应边界（top++ / bottom-- / right-- / left++）
直到元素全部收集

48. 旋转图像#

题目描述： 给定一个 n × n 的二维矩阵 matrix 表示一个图像，将图像顺时针旋转 90 度。要求必须在原地旋转图像，也就是说，你需要直接修改输入的二维矩阵。

思路：转置 + 水平翻转，O(1) 空间

转置：交换 matrix[i][j] 和 matrix[j][i]（只遍历上三角，i < j）
水平翻转：每行左右镜像，交换 matrix[i][j] 和 matrix[i][n-1-j]（只遍历左半列）

两步合计即为顺时针旋转 90°。

240. 搜索二维矩阵II#

题目描述： 在一个 m x n 矩阵中查找目标值 target；矩阵每行从左到右升序排列，每列从上到下升序排列。

思路：从右上角出发，利用单调性 O(m+n)

从右上角 (0, n-1) 出发
当前值 > target → 左移（col--，排除当前列）
当前值 < target → 下移（row++，排除当前行）
当前值 = target → 找到返回 true
越界退出返回 false

链表#

160. 相交链表#

题目描述： 给你两个单链表的头节点 headA 和 headB，请找出并返回它们相交的起始节点；如果两个链表没有相交，则返回 null。

思路：双指针消除长度差

pA, pB 分别从两链表头出发
走完自己的链表后接到另一条链表的头部继续走
两指针走过路程相等时相遇（有交叉则在交叉点，无交叉则同时到 null）

时间 O(m+n)，空间 O(1)。

206. 反转链表#

题目描述： 给你单链表的头节点 head，请你反转链表，并返回反转后的链表。

思路：迭代，三指针翻转

prev=null, curr=head
循环：next = curr.next → curr.next = prev → prev = curr → curr = next
返回 prev

递归版：先递归到末尾，返回新头；回溯时 head.next.next = head，head.next = null。

234. 回文链表#

题目描述： 给你一个单链表的头节点 head，请判断该链表是否为回文链表。

思路：快慢指针找中点 + 反转后半

快慢指针找到后半段起点（快指针每次走两步，慢指针走一步）
反转后半段链表
双指针从头和后半起点同步比较，有不同则非回文
可选：复原后半段（面试时常见要求）

141. 环形链表#

题目描述： 给你一个链表的头节点 head，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。

思路：快慢指针判圈（Floyd）

slow 每次走 1 步，fast 每次走 2 步
fast 或 fast.next 为 null → 无环，返回 false
fast == slow → 有环，返回 true

142. 环形链表II#

题目描述： 给定一个链表的头节点 head，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

思路：Floyd 判圈找入口

快慢指针相遇后（有环），将 slow 重置为 head
slow 和 fast 同时以步长 1 前进
再次相遇的节点即为入环点（数学证明：相遇点到入环点的距离 = 头到入环点的距离）

21. 合并两个有序链表#

题目描述： 将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

思路：虚拟头节点 + 迭代比较

dummy 虚拟头节点，cur = dummy
两链表均非空时：比较当前节点值，较小的接到 cur.next，对应链表指针后移，cur = cur.next
任一链表遍历完后，将另一链表剩余部分直接接到 cur.next

2. 两数相加#

题目描述： 给你两个非空的链表，表示两个非负的整数。它们每个节点存储一个数字，并且是按照逆序方式存储的。请你将这两个数相加，并以相同形式返回一个表示和的链表。

思路：模拟竖式加法，同步遍历两链表

carry=0，虚拟头节点
循环直到两链表均为空且 carry==0：取两链表当前值（为空则取 0），sum = val1 + val2 + carry，新节点值 = sum % 10，carry = sum / 10
每次推进两链表指针

19. 删除链表的倒数第N个结点#

题目描述： 给你一个链表的头节点 head 和一个整数 n ，请你删除链表的倒数第 n 个结点，并且返回链表的头结点。

思路：快慢指针，快指针先走 N 步

dummy 虚拟头节点，fast=dummy, slow=dummy
fast 先走 N+1 步（多走一步使 slow 最终停在目标前驱）
fast 和 slow 同步前进直到 fast==null
slow.next = slow.next.next（删除目标节点）

24. 两两交换链表中的节点#

题目描述： 给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。注意：你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

思路：虚拟头节点 + 迭代交换相邻节点 每次处理 prev → A → B → rest，交换为 prev → B → A → rest：

prev.next = B
A.next = B.next
B.next = A
prev = A（A 变成下一组的前驱）

25. K个一组翻转链表#

题目描述： 给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

思路：截取 K 个反转后重接，递归或迭代

先检查后续是否有 K 个节点，不足则直接返回
截取前 K 个节点，执行链表反转（206 题方法）
原头节点（反转后变尾节点）的 next 接上递归处理剩余链表的结果
返回新头节点（原第 K 个节点）

138. 复制带随机指针的链表#

题目描述： 给你一个长度为 n 的链表，每个节点包含一个额外的随机指针 random ，该指针可以指向链表中的任意节点或空节点。请构造这个链表的深拷贝，并返回拷贝链表的头节点。

思路：哈希表存原节点 → 新节点映射

第一遍：遍历原链表，为每个节点创建对应新节点，存入哈希表
第二遍：遍历原链表，通过哈希表设置每个新节点的 next 和 random 指针

时间 O(n)，空间 O(n)。

148. 排序链表#

题目描述： 给你链表的头结点 head ，请将其按升序排列并返回排序后的链表。进阶要求时间复杂度为 O(n log n)，且尽量使用常数级空间复杂度。

思路：归并排序（自顶向下）

快慢指针找链表中点，将链表从中点断开
递归排序左右两段
合并两段有序链表（21 题方法）

时间 O(n log n)，递归栈空间 O(log n)；迭代版本（自底向上合并）可达 O(1) 空间。

23. 合并K个升序链表#

题目描述： 给你一个链表数组，每个链表都已经按升序排列。请将所有链表合并到一个升序链表中，并返回合并后的链表头节点。

思路：小根堆维护各链表当前最小节点

将所有链表头节点加入小根堆（按节点值排序）
每次取堆顶（当前所有链表中最小节点），接入结果链
将该节点的 next（若非空）加入堆
直到堆为空

时间 O(n log k)，n 为总节点数，k 为链表数。

146. LRU缓存#

题目描述： 设计并实现一个 LRUCache，支持 get(key) 和 put(key, value)；当缓存容量超出限制时，淘汰最近最少使用的键，并要求两个操作都在 O(1) 时间内完成。

思路：哈希表 + 双向链表

双向链表维护使用顺序：头部最近使用，尾部最久未用
哈希表 key → 链表节点，O(1) 定位

get(key)：在哈希表中找到节点，将其移动到链表头部，返回值。 put(key, val)：若 key 存在则更新并移到头部；否则创建新节点插入头部，同时存入哈希表；若超容量则删除链表尾部节点并从哈希表中移除。

二叉树#

94. 二叉树的中序遍历#

题目描述： 给定一个二叉树的根节点 root ，返回它的中序遍历结果。中序遍历的访问顺序为：左子树、根节点、右子树。

迭代思路（面试重点）：

stack = []，cur = root
循环：若 cur != null，将 cur 压栈并走到 cur.left；否则弹出栈顶，加入结果，令 cur = 弹出节点.right
直到 cur==null 且栈为空

104. 二叉树的最大深度#

题目描述： 给定一个二叉树 root ，返回其最大深度。二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数。

递归思路：

maxDepth(root) = 0                              // root == null
              = 1 + max(maxDepth(left), maxDepth(right))  // 否则

plaintext

BFS 层序遍历逐层计数也可。

226. 翻转二叉树#

题目描述： 给你一棵二叉树的根节点 root ，请你翻转这棵二叉树，并返回其根节点。

递归思路：

invertTree(root):
    if root == null: return null
    root.left, root.right = invertTree(root.right), invertTree(root.left)
    return root

plaintext

101. 对称二叉树#

题目描述： 给你一个二叉树的根节点 root ，检查它是否轴对称。

思路：递归比较镜像节点对 定义辅助函数 isMirror(left, right)：

两者均为 null → true
一者为 null 或值不等 → false
递归：isMirror(left.left, right.right) && isMirror(left.right, right.left)

543. 二叉树的直径#

题目描述： 给定一棵二叉树，你需要计算它的直径长度。二叉树的直径是任意两个节点路径长度中的最大值，这条路径可能经过也可能不经过根节点。这里的路径长度指两节点之间边的数目。

思路：后序 DFS，每节点计算左右最大深度之和

DFS 函数返回以当前节点为根的最大深度
在每个节点处：直径候选 = left深度 + right深度，更新全局最大
返回给父节点：1 + max(left, right)

102. 二叉树的层序遍历#

题目描述： 给你二叉树的根节点 root ，返回其节点值的层序遍历结果，即逐层地从左到右访问所有节点。

思路：BFS，按层收集

初始队列放入 root
每轮循环处理当前队列中所有节点（当前层）：逐一出队，值加入当前层结果，左右子节点非空则入队
将当前层结果加入总结果

108. 将有序数组转换为二叉搜索树#

题目描述： 给你一个整数数组 nums ，其中元素已经按升序排列，请你将其转换为一棵高度平衡二叉搜索树并返回根节点。

思路：递归取中间元素为根

取 mid = (left + right) / 2 作为根节点
递归构造左子树：[left, mid-1]
递归构造右子树：[mid+1, right]

取中点保证高度平衡，可选 mid = (left + right + 1) / 2 偏右也合法。

98. 验证二叉搜索树#

题目描述： 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。有效二叉搜索树满足：节点左子树只包含小于当前节点的数，右子树只包含大于当前节点的数，且左右子树本身也都必须是二叉搜索树。

思路：递归传入合法范围 [min, max]

isValid(node, min, max):
    if node == null: return true
    if node.val <= min or node.val >= max: return false
    return isValid(node.left, min, node.val) && isValid(node.right, node.val, max)

plaintext

调用：isValid(root, -∞, +∞)

230. 二叉搜索树中第K小的元素#

题目描述： 给定一棵二叉搜索树 root 和一个整数 k，请返回这棵树中第 k 小的节点值。

思路：中序遍历 BST（迭代，提前终止） 用中序遍历迭代模板（参考 94 题），维护计数器 count，每次弹出节点时 count++，count == k 时返回当前节点值。

199. 二叉树的右视图#

题目描述： 给定一棵二叉树的根节点 root，返回从右侧观察这棵树时，按从上到下顺序能看到的节点值。

思路：BFS 层序遍历，取每层最后一个节点 层序遍历时，每层最后一个出队的节点值即为右视图（参考 102 题，在每层循环的最后一次迭代时记录值）。

114. 二叉树展开为链表#

题目描述： 给定一个二叉树的根节点，原地将它展开为一个单链表，展开后的链表顺序应与二叉树的前序遍历顺序一致。所有节点的右子指针指向下一个节点，左子指针始终为null。

思路：反向后序遍历（右→左→根），维护 prev 指针

按 右→左→根 顺序 DFS
每访问一个节点：node.right = prev，node.left = null，prev = node
遍历结束后链表已就绪（无需额外操作）

105. 从前序与中序遍历序列构造二叉树#

题目描述： 给定两个整数数组preorder和inorder，其中preorder是二叉树的前序遍历，inorder是同一棵树的中序遍历，请构造并返回这颗二叉树。

思路：递归，前序首元素定根，中序划分左右子树

前序首元素为根，在中序中查找根的位置（用哈希表预存 O(1) 查找）
中序根左侧为左子树（长度设为 leftSize），右侧为右子树
前序中 [1, 1+leftSize) 对应左子树，[1+leftSize, ...] 对应右子树
递归构造

437. 路径总和III#

题目描述： 给定一个二叉树的根节点 root 和一个整数 targetSum，返回该二叉树中路径和等于 targetSum 的路径数目。路径不需要从根节点开始，也不需要在叶子节点结束，但必须是从父节点到子节点的方向。

思路：DFS + 前缀和哈希表（不要求从根开始）

哈希表存 {路径前缀和 → 出现次数}，初始化 {0: 1}
DFS 遍历，curSum += node.val
查哈希表中 curSum - targetSum 的次数，累加到答案
将 curSum 存入哈希表，递归左右子树，回溯时将 curSum 从哈希表中移除（撤销）

236. 二叉树的最近公共祖先#

题目描述： 给定一个二叉树，找到该树中两个指定节点 p 和 q 的最近公共祖先。最近公共祖先的定义为：对于有根树 T 的两个节点 p、q，最近公共祖先表示一个节点 x，满足 x 是 p、q 的祖先，且 x 的深度尽可能大。

思路：后序 DFS，从子树向上报告

LCA(root, p, q):
    if root == null or root == p or root == q: return root
    left = LCA(root.left, p, q)
    right = LCA(root.right, p, q)
    if left != null and right != null: return root  // 两侧各有一个
    return left if left != null else right           // 都在同侧

plaintext

124. 二叉树中的最大路径和#

题目描述： 二叉树中的路径被定义为一条从树中任意节点出发，沿父子连接到达任意节点的序列。同一个节点在一条路径中至多出现一次，且路径至少包含一个节点。给定二叉树的根节点 root ，返回其中路径和的最大值。

思路：后序 DFS，区分”过当前节点的路径”和”向上贡献”

DFS 函数返回「以当前节点为端点向上的最大贡献值」= node.val + max(0, left贡献, right贡献)
在每个节点处更新全局答案：node.val + max(0, left) + max(0, right)（路径可在此节点转弯）
注意贡献值可为负时取 0（不选该子树）

图论#

200. 岛屿数量#

题目描述： 给你一个由字符 '1'（陆地）和 '0'（水）组成的二维网格 grid ，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平或垂直方向上相邻的陆地连接形成。

思路：DFS/BFS 淹没已访问的岛屿

遍历网格，遇到 '1' 时启动 DFS，计数 +1
DFS：将当前格子置 '0'，递归访问四个方向（越界或为 '0' 则返回）
每次 DFS 将整块相连的陆地全部淹没

994. 腐烂的橘子#

题目描述： 在给定的 m x n 网格 grid 中，每个单元格可能有以下三种值之一：0 代表空单元格，1 代表新鲜橘子，2 代表腐烂橘子。每分钟，腐烂橘子会使其四个方向上相邻的新鲜橘子腐烂。请返回直到网格中没有新鲜橘子为止所需的最小分钟数；如果无法做到，返回 -1。

思路：多源 BFS，同时扩散

将所有初始腐烂橘子坐标入队，统计新鲜橘子数 fresh
BFS 逐层扩散（每层代表 1 分钟），每腐烂一个新鲜橘子 fresh--
BFS 结束后：若 fresh > 0 返回 -1，否则返回经过的分钟数

207. 课程表#

题目描述： 你这个学期必须选修 numCourses 门课程，课程编号为 0 到 numCourses - 1 。给定一个数组 prerequisites ，其中 prerequisites[i] = [ai, bi] 表示如果要学习课程 ai 就必须先完成课程 bi 。请判断是否可能完成所有课程。

思路：拓扑排序（BFS + Kahn 算法）

建立邻接表，统计每个节点的入度
将所有入度为 0 的节点加入队列
BFS：每次取出节点，遍历其邻居，邻居入度 -1，若邻居入度变为 0 则入队
计数处理的节点数，若等于总节点数则无环（可完成所有课程）

208. 实现 Trie（前缀树）#

题目描述： 请你实现 Trie（前缀树）类，支持以下操作：insert(String word) 插入字符串，search(String word) 判断字符串是否在前缀树中，startsWith(String prefix) 判断是否存在以给定前缀开头的字符串。

思路：每个节点含 26 个子节点 + isEnd 标志

insert(word)：逐字符遍历，若子节点不存在则创建，最后标记 isEnd=true
search(word)：逐字符遍历，任一字符对应子节点不存在则返回 false，遍历完检查 isEnd
startsWith(prefix)：同 search，但最后不检查 isEnd，只需路径存在即可

回溯#

46. 全排列#

题目描述： 给定一个不含重复数字的整数数组 nums ，返回其所有可能的全排列。你可以按任意顺序返回答案。

思路：回溯 + used 数组

backtrack(path):
    if len(path) == n: 记录结果并返回
    for i in range(n):
        if used[i]: continue
        used[i] = true; path.append(nums[i])
        backtrack(path)
        used[i] = false; path.pop()

plaintext

78. 子集#

题目描述： 给定一个整数数组 nums ，其中元素互不相同，返回该数组所有可能的子集（幂集）。解集不能包含重复的子集，答案顺序可以任意。

思路：回溯，每层从 start 开始枚举，无需终止条件

backtrack(start, path):
    记录当前 path（空集也记录）
    for i in range(start, n):
        path.append(nums[i])
        backtrack(i+1, path)
        path.pop()

plaintext

17. 电话号码的字母组合#

题目描述： 给定一个仅包含数字 2-9 的字符串 digits ，返回它能表示的所有字母组合。答案可以按任意顺序返回；如果 digits 为空，返回空列表。

思路：回溯，每层选当前数字对应字母

backtrack(index, path):
    if index == len(digits): 记录 path 并返回
    for ch in mapping[digits[index]]:
        path.append(ch)
        backtrack(index+1, path)
        path.pop()

plaintext

39. 组合总和#

题目描述： 给定一个无重复元素的整数数组 candidates 和一个目标整数 target ，找出 candidates 中所有和为 target 的不同组合。数组中的同一个数字可以被无限次选取，但解集不能包含重复组合。

思路：回溯，允许重复选，当前元素可重复

backtrack(start, path, remain):
    if remain == 0: 记录结果并返回
    for i in range(start, n):
        if nums[i] > remain: break  // 排序后剪枝
        path.append(nums[i])
        backtrack(i, path, remain - nums[i])  // i 不是 i+1，允许重复选
        path.pop()

plaintext

22. 括号生成#

题目描述： 给定 n 对括号，请你生成并返回所有可能的有效括号组合。答案可以按任意顺序返回。

思路：回溯，维护左/右括号剩余数量

backtrack(path, open, close):
    if len(path) == 2*n: 记录结果
    if open > 0: 加 '(' → backtrack → 退
    if close > open: 加 ')' → backtrack → 退

plaintext

open = 还能放的左括号数，close = 还能放的右括号数，初始均为 n。

79. 单词搜索#

题目描述： 给定一个 m x n 的字符网格 board 和一个字符串 word ，判断 word 是否存在于网格中。单词必须通过相邻单元格内的字母构成，相邻单元格是水平或垂直相邻的，同一个单元格内的字母不能被重复使用。

思路：DFS + 回溯，标记访问防止重复

dfs(i, j, k):  // k 为当前匹配的字符索引
    if k == len(word): return true
    if 越界 or 已访问 or grid[i][j] != word[k]: return false
    标记 grid[i][j] 为已访问（如置 '#'）
    result = dfs(四方向)
    恢复 grid[i][j]
    return result

plaintext

遍历所有格子作为起点尝试。

131. 分割回文串#

题目描述： 给定一个字符串 s ，请将 s 分割成一些子串，使每个子串都是回文串，并返回 s 所有可能的分割方案。

思路：DP 预处理 + 回溯枚举分割点

先用 DP 求 isPalin[i][j]（s[i..j] 是否为回文）
回溯：从 start 开始枚举右端点 end，若 isPalin[start][end] 则将该段加入路径，递归处理 end+1 之后的部分

51. N皇后#

题目描述： 按照 n 皇后问题的规则，在 n x n 的棋盘上放置 n 个皇后，并返回所有不同的解法。每一种解法包含一个棋盘布局，其中 Q 表示皇后，. 表示空位。

思路：逐行回溯，三个集合记录占用

用 cols、diag1（正对角线 row-col）、diag2（反对角线 row+col）三个集合记录已放置皇后的攻击范围
每行枚举合法列，不与已有皇后冲突则放置
放置后更新三集合，递归下一行，回溯时撤销

二分查找#

35. 搜索插入位置#

题目描述： 给定一个升序排列的整数数组 nums 和一个目标值 target ，在数组中查找目标值。如果目标值存在，返回它的下标；如果不存在，返回它应该按顺序插入的位置。

思路：标准左闭右闭二分，找第一个 ≥ target 的位置

left=0, right=n-1
while left <= right:
    mid = (left+right)//2
    if nums[mid] < target: left = mid+1
    else: right = mid-1
return left

plaintext

74. 搜索二维矩阵#

题目描述： 给你一个满足以下条件的 m x n 整数矩阵 matrix ：每行中的整数从左到右按升序排列，且每行的第一个整数大于前一行的最后一个整数。给定一个目标值 target ，判断 target 是否在矩阵中。

思路：将矩阵映射为一维，直接二分

矩阵有 m 行 n 列，视为长度 m×n 的有序数组
mid 对应 matrix[mid // n][mid % n]
其余与标准二分相同

34. 在排序数组中查找元素的第一个和最后一个位置#

题目描述： 给定一个按照非递减顺序排列的整数数组 nums 和一个目标值 target ，找出 target 在数组中的起始位置和结束位置。如果数组中不存在目标值，返回 [-1, -1]。题目要求算法时间复杂度为 O(log n)。

思路：两次二分，分别找左边界和右边界

找左边界：nums[mid] == target 时不停，令 right = mid - 1，循环结束时 left 即为左边界
找右边界：nums[mid] == target 时令 left = mid + 1，循环结束时 right 即为右边界
最后检查左边界是否合法（是否 == target）

33. 搜索旋转排序数组#

题目描述： 整数数组 nums 按升序排列，数组中的值互不相同。在传入函数前，nums 在某个下标 k 处发生旋转，使数组变为旋转后的升序数组。给定旋转后的数组 nums 和目标值 target ，如果 target 存在则返回其下标，否则返回 -1。题目要求时间复杂度为 O(log n)。

思路：二分时先判断哪段有序，再判断 target 在哪段

if nums[left] <= nums[mid]:  // 左段有序
    if nums[left] <= target < nums[mid]: right = mid-1
    else: left = mid+1
else:  // 右段有序
    if nums[mid] < target <= nums[right]: left = mid+1
    else: right = mid-1

plaintext

153. 寻找旋转排序数组中的最小值#

题目描述： 已知长度为 n 的数组 nums 按升序排列，数组中的值互不相同。在传入函数前，nums 在某个下标处发生旋转。请你找出并返回旋转后数组中的最小元素，要求时间复杂度为 O(log n)。

思路：二分，比较 mid 与 right

while left < right:
    mid = (left+right)//2
    if nums[mid] > nums[right]: left = mid+1   // 最小值在右半
    else: right = mid                           // 最小值在左半（含 mid）
return nums[left]

plaintext

4. 寻找两个正序数组的中位数#

题目描述： 给定两个大小分别为 m 和 n 的正序数组 nums1 和 nums2 ，请你找出并返回这两个正序数组的中位数。题目要求算法的时间复杂度为 O(log(m + n))。

思路：二分较短数组的划分位置

在较短数组 A 中二分划分位置 i，使得 i + j = (m+n+1)/2（j 为 B 的划分位置）
保证 A[i-1] ≤ B[j] 且 B[j-1] ≤ A[i]（交叉比较）
不满足时调整 i 的范围
满足后，左半最大值和右半最小值即可计算中位数

时间 O(log min(m, n))。

栈#

20. 有效的括号#

题目描述： 给定一个只包含 (、)、{、}、[、] 的字符串 s ，判断字符串是否有效。有效字符串需满足：左括号必须用相同类型的右括号闭合，左括号必须以正确的顺序闭合。

思路：栈匹配左右括号

遍历字符串
遇左括号 (, [, { → 入栈
遇右括号 → 检查栈是否为空且栈顶是否为对应左括号；否则返回 false
最终栈为空则合法

155. 最小栈#

题目描述： 设计一个支持 push、pop、top 和 getMin 操作的栈，并保证每个操作都能在 O(1) 时间复杂度内完成。

思路：辅助栈同步记录当前最小值

push(val)：主栈正常压入；辅助栈压入 min(val, 辅助栈顶)（辅助栈为空则直接压 val）
pop()：两栈同步弹出
getMin()：返回辅助栈顶

394. 字符串解码#

题目描述： 给定一个经过编码的字符串 s ，按照规则 k[encoded_string] 进行解码并返回结果，其中方括号内的字符串会被重复 k 次。输入保证格式合法，且不会出现额外空格。

思路：栈存储上下文，遇 [ 入栈，遇 ] 弹出拼接

维护当前字符串 curStr 和当前数字 curNum
遇数字字符：curNum = curNum * 10 + digit
遇 [：将 (curStr, curNum) 压栈，重置 curStr="", curNum=0
遇 ]：弹出 (prevStr, num)，curStr = prevStr + num * curStr
遇普通字母：curStr += ch

739. 每日温度#

题目描述： 给定一个整数数组 temperatures ，表示每天的温度。请返回一个数组 answer ，其中 answer[i] 表示在第 i 天之后，至少还需要等待多少天才能出现更高的气温；如果之后都不会升高，则该位置为 0。

思路：单调递减栈（存下标），遇到更高温度时结算

维护单调递减栈（栈内温度从底到顶递减）
遍历 i：当 stack 非空且 temp[i] > temp[stack.top()] 时，弹出 j，result[j] = i - j，循环直到满足单调性
将 i 压栈
最后栈中剩余下标对应结果为 0（默认值）

84. 柱状图中最大的矩形#

题目描述： 给定 n 个非负整数表示柱状图中各柱子的高度，每个柱子宽度为 1，请返回柱状图中能勾勒出的矩形的最大面积。

思路：单调递增栈（存下标），维护每个柱子的左边界

在数组首尾各补一个高度为 0 的哨兵柱（简化边界处理）
维护单调递增栈：遇到比栈顶矮的柱子 heights[i] 时，弹出栈顶 top：
- 高度 = heights[top]
- 宽度 = i - stack.peek() - 1（新栈顶为左边界）
- 更新最大面积
将 i 压栈

堆#

215. 数组中的第K个最大元素#

题目描述： 给定整数数组 nums 和整数 k ，请返回数组中第 k 个最大的元素。这里指的是排序后的第 k 个最大元素，而不是第 k 个不同的元素。

思路一：小根堆，维护堆大小为 K

将前 K 个元素建小根堆
遍历剩余元素：若 > 堆顶则替换堆顶并调整
最终堆顶即为第 K 大

思路二：快速选择（平均 O(n)） 每次 partition 将数组分为 > pivot 和 < pivot 两部分，根据 pivot 最终位置递归进入正确的一侧。

347. 前K个高频元素#

题目描述： 给定一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。答案可以按任意顺序返回。

思路：哈希表统计频次 + 小根堆（按频次）

哈希表统计每个元素的频次
遍历哈希表，维护大小为 K 的小根堆（按频次排序）
若堆满且当前频次 > 堆顶频次，替换堆顶
最终堆中 K 个元素即为答案

桶排序方案：以频次为下标建 n+1 个桶，O(n) 时间。

295. 数据流的中位数#

题目描述： 中位数是有序整数列表中的中间值。如果列表长度为偶数，中位数是中间两个数的平均值。请设计一个支持以下操作的数据结构：addNum(int num) 用于向数据流中添加整数，findMedian() 用于返回当前所有元素的中位数。

思路：大根堆 + 小根堆，维护两堆大小平衡

maxHeap（大根堆）存较小的一半，minHeap（小根堆）存较大的一半
约束：maxHeap.size == minHeap.size 或 maxHeap.size == minHeap.size + 1

addNum(num)：先加入 maxHeap，再将 maxHeap 堆顶移到 minHeap，若 minHeap 更大则将其堆顶移回 maxHeap findMedian()：若两堆等大取两堆顶均值，否则返回 maxHeap 堆顶

贪心算法#

121. 买卖股票的最佳时机#

题目描述： 给定一个数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。你只能选择某一天买入这只股票，并在未来某一天卖出，最多进行一次交易。请返回你能获得的最大利润；如果无法获得利润，返回 0。

思路：一次遍历，维护历史最低价

minPrice = ∞，maxProfit = 0
遍历每天价格：minPrice = min(minPrice, price)，maxProfit = max(maxProfit, price - minPrice)
返回 maxProfit

55. 跳跃游戏#

题目描述： 给定一个非负整数数组 nums ，你最初位于数组的第一个下标。数组中的每个元素表示你在该位置可以向前跳跃的最大长度。请判断你是否能够到达最后一个下标。

思路：维护可达最远下标

maxReach = 0
遍历 i：若 i > maxReach 则无法到达，返回 false；否则 maxReach = max(maxReach, i + nums[i])
遍历完返回 true

45. 跳跃游戏II#

题目描述： 给定一个长度为 n 的非负整数数组 nums ，你最初位于第一个下标。数组中的每个元素表示你在该位置可以跳跃的最大长度。请返回到达最后一个下标的最少跳跃次数。

思路：贪心，每次跳到当前范围内能到达最远的位置

jumps=0, curEnd=0, farthest=0
遍历 i（不含最后一个位置）：farthest = max(farthest, i + nums[i])
当 i == curEnd 时必须跳一次：jumps++，curEnd = farthest，若 curEnd >= n-1 可提前结束

763. 划分字母区间#

题目描述： 给定一个字符串 s ，请尽可能多地划分为若干片段，使得每个字母最多出现在一个片段中。返回一个表示每个片段长度的列表。

思路：记录每个字符最后出现位置 + 贪心扩展区间

遍历字符串，记录每个字符最后出现的下标 last[ch]
再次遍历：维护当前区间右边界 end = max(end, last[s[i]])，到达 i == end 时切分：区间长度 = i - start + 1，start = i + 1

动态规划（单维）#

70. 爬楼梯#

题目描述： 假设你正在爬楼梯，需要 n 阶才能到达楼顶。每次你可以爬 1 阶或 2 阶，请问有多少种不同的方法可以爬到楼顶。

状态： dp[i] = 到第 i 阶的方法数 转移： dp[i] = dp[i-1] + dp[i-2]（最后一步跨 1 或跨 2） 初始： dp[1]=1, dp[2]=2；滚动变量 a, b 优化空间

118. 杨辉三角#

题目描述： 给定一个非负整数 numRows ，生成「杨辉三角」的前 numRows 行。

思路： 每行首尾为 1，中间元素 triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j]，逐行生成。

198. 打家劫舍#

题目描述： 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都有一定金额的现金，但相邻的两间房屋装有联动报警系统，如果同一晚闯入相邻的两间房，系统就会报警。给定一个代表每间房存放金额的整数数组 nums ，返回在不触发警报的情况下你能够偷窃到的最高金额。

状态： dp[i] = 前 i 间房能偷的最大金额 转移： dp[i] = max(dp[i-1], dp[i-2] + nums[i])（不偷当前 or 偷当前） 初始： dp[0]=nums[0], dp[1]=max(nums[0], nums[1])

279. 完全平方数#

题目描述： 给定一个整数 n，返回和为 n 的完全平方数的最少数量。完全平方数指某个整数自乘得到的数，例如 1、4、9、16。

状态： dp[i] = 和为 i 所需最少完全平方数数量 转移： dp[i] = min(dp[i - j*j] + 1)，枚举所有 j*j ≤ i 初始： dp[0]=0，其余为 ∞

322. 零钱兑换#

题目描述： 给定不同面额的硬币数组 coins 和一个总金额 amount ，计算可以凑成总金额所需的最少硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

状态： dp[i] = 凑成金额 i 所需最少硬币数 转移： dp[i] = min(dp[i - coin] + 1)，枚举所有面额 初始： dp[0]=0，其余为 ∞；无法凑成则返回 -1

139. 单词拆分#

题目描述： 给定一个非空字符串 s 和一个包含非空单词的列表 wordDict ，判断 s 是否可以被空格拆分为一个或多个在字典中出现的单词。字典中的单词可以重复使用。

状态： dp[i] = 前 i 个字符是否能被字典中单词拆分 转移： dp[i] = true 若存在 j < i 使得 dp[j] == true 且 s[j:i] 在字典中 初始： dp[0]=true（空串）

300. 最长递增子序列#

题目描述： 给定一个整数数组 nums ，找到其中最长严格递增子序列的长度。子序列是由数组派生而来的序列，删除若干元素或不删除元素但不改变其余元素顺序。

O(n²) DP： dp[i] = 以 nums[i] 结尾的 LIS 长度，dp[i] = max(dp[j]+1) 对所有 j<i 且 nums[j]<nums[i]

O(n log n) 贪心+二分： 维护 tails 数组，tails[k] 为长度为 k+1 的递增子序列末尾最小值，遍历时二分找到第一个 ≥ nums[i] 的位置替换或追加。

152. 乘积最大子数组#

题目描述： 给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组，并返回该子数组对应的乘积。

状态： 同时维护 maxProd（以当前结尾的最大乘积）和 minProd（最小乘积，为负数时乘负值可变最大） 转移：

newMax = max(nums[i], maxProd * nums[i], minProd * nums[i])
newMin = min(nums[i], maxProd * nums[i], minProd * nums[i])

plaintext

更新全局 result = max(result, newMax)

416. 分割等和子集#

题目描述： 给定一个只包含正整数的非空数组 nums ，请判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

思路：0/1 背包，目标容量 = 总和 / 2

若总和为奇数则直接返回 false
dp[j] = 能否用数组中的数凑成容量 j
对每个 nums[i]，逆序遍历 j：dp[j] = dp[j] || dp[j - nums[i]]
返回 dp[target]

32. 最长有效括号#

题目描述： 给定一个只包含 ( 和 ) 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

状态： dp[i] = 以 s[i] 结尾的最长有效括号长度（s[i] 为 ) 时才可能非零） 转移：

若 s[i-1] == '('：dp[i] = dp[i-2] + 2
若 s[i-1] == ')' 且 s[i - dp[i-1] - 1] == '('：dp[i] = dp[i-1] + 2 + dp[i - dp[i-1] - 2]（加上前一个有效段的长度）

多维动态规划#

62. 不同路径#

题目描述： 一个机器人位于一个 m x n 网格的左上角，每次只能向下或者向右移动一步。机器人试图到达网格的右下角。请问总共有多少条不同的路径。

状态： dp[i][j] = 从左上角到 (i,j) 的路径数 转移： dp[i][j] = dp[i-1][j] + dp[i][j-1] 初始： 第一行和第一列全为 1（只能直走）

64. 最小路径和#

题目描述： 给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使路径上的数字总和最小。说明：每次只能向下或者向右移动一步。

状态： dp[i][j] = 从左上角到 (i,j) 的最小路径和 转移： dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j] 初始： 第一行和第一列累加前缀和；可原地修改 grid 节省空间

5. 最长回文子串#

题目描述： 给你一个字符串 s ，找到 s 中最长的回文子串，并将其返回。

思路一：中心扩展（推荐，O(n²) 时间 O(1) 空间） 以每个字符（奇数长度）和相邻两字符间（偶数长度）为中心向两侧扩展，记录最长回文的起止位置。

思路二：DP dp[i][j] = s[i..j] 是否为回文，转移：dp[i][j] = (s[i]==s[j]) && dp[i+1][j-1]，按长度从小到大枚举。

1143. 最长公共子序列#

题目描述： 给定两个字符串 text1 和 text2 ，返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列，返回 0。

状态： dp[i][j] = s1 前 i 个字符与 s2 前 j 个字符的 LCS 长度 转移：

s1[i-1] == s2[j-1]：dp[i][j] = dp[i-1][j-1] + 1
否则：dp[i][j] = max(dp[i-1][j], dp[i][j-1])

72. 编辑距离#

题目描述： 给你两个单词 word1 和 word2 ，请返回将 word1 转换成 word2 所使用的最少操作数。你可以对一个单词进行插入、删除或替换一个字符三种操作。

状态： dp[i][j] = 将 word1 前 i 个字符转为 word2 前 j 个字符的最少操作数 转移：

word1[i-1] == word2[j-1]：dp[i][j] = dp[i-1][j-1]（无需操作）
否则：dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])（删除/插入/替换） 初始： dp[i][0] = i，dp[0][j] = j

技巧#

136. 只出现一次的数字#

题目描述： 给定一个非空整数数组 nums ，除某个元素只出现一次以外，其余每个元素均出现两次。请找出那个只出现一次的元素。

思路：全部异或 所有数异或，相同数字消为 0，最终剩下只出现一次的数字。时间 O(n)，空间 O(1)。

169. 多数元素#

题目描述： 给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数大于 ⌊n / 2⌋ 的元素。

思路：Boyer-Moore 投票算法

candidate=nums[0], count=1
遍历：count==0 则换候选者；nums[i]==candidate 则 count++，否则 count--
最终 candidate 即为多数元素（出现次数 > n/2 保证其存活）

75. 颜色分类#

题目描述： 给定一个包含红色、白色和蓝色共 n 个元素的数组 nums ，请你原地对它们进行排序，使相同颜色的元素相邻，并按照红、白、蓝的顺序排列。我们使用整数 0、1 和 2 分别表示红色、白色和蓝色。

思路：三路划分（荷兰国旗问题），三指针一次遍历

low=0, mid=0, high=n-1
遍历 mid 直到 mid > high：
- nums[mid]==0：与 nums[low] 交换，low++, mid++
- nums[mid]==2：与 nums[high] 交换，high--（mid 不动，因为换来的数未检查）
- nums[mid]==1：mid++

31. 下一个排列#

题目描述： 整数数组的一个排列就是将其所有成员以序列或线性顺序排列。给定一个整数数组 nums ，需要将其修改为下一个按字典序更大的排列。如果不存在下一个更大的排列，则将其重新排列成字典序最小的排列。要求必须原地修改，只允许使用常数额外空间。

思路：从右找下降点，交换后反转尾部

从右找第一个下降点 i（nums[i] < nums[i+1]）
若 i 存在：从右找第一个 j 使得 nums[j] > nums[i]，交换 nums[i] 和 nums[j]
反转 i+1 到末尾（使后缀变为最小升序）
若 i 不存在（整个数组降序）：直接反转整个数组

287. 寻找重复数#

题目描述： 给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内。可知至少存在一个重复的整数，请你找出这个重复的数。题目要求不能修改数组，并尽量只使用常量级额外空间。

思路：Floyd 判圈算法（类比环形链表II） 将数组值视为”下一跳”指针（index → nums[index]），由于存在重复数，必然形成环。