1. 从两道题说起：为什么它们总被放在一起考
"找出数组中重复的数"和"二维数组中的查找"，这两道题放在一起看，其实特别有意思。前者考的是你对原地算法和空间换时间的理解，后者考的是你对数据有序性的敏感度。它们都属于那种"看起来简单，写起来容易翻车"的典型题目。
我第一次接触这两道题的时候，心里想的是：这不就是遍历吗？一个用哈希表，一个逐行二分，能有多难？结果面试的时候被追问"能不能不用额外空间"、"时间复杂度能不能再降"，当场就卡壳了。后来刷题刷多了才发现，这两道题背后藏着的东西远比表面看起来深——它们分别对应了数组类问题的两大核心思路：下标映射和有序性利用。
这篇文章我会把这两道题彻底拆开，从暴力解法一路讲到最优解，把每一步的思考过程、参数选择、边界处理都讲清楚。不管你是刚开始刷题的新手，还是想重新梳理思路的老手，应该都能从中找到有用的东西。尤其是那些"为什么这么想"的部分，我会尽量讲透，因为解题思路比代码本身重要得多。
2. 找出数组中重复的数：从哈希表到原地交换
2.1 题目描述与核心约束
先把题目说清楚。给定一个长度为 n 的数组 nums，里面所有数字都在 0 到 n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。要求找出数组中任意一个重复的数字。
举个例子：nums = [2, 3, 1, 0, 2, 5, 3]，长度是 7，所有数字都在 0 到 6 之间。这里面 2 和 3 都是重复的，返回其中任意一个就行。
这道题有一个非常关键的约束：数字范围是 0 到 n-1。很多人第一眼看到这个条件会忽略掉，觉得只是个普通的数组。但恰恰是这个条件，决定了你能不能写出空间复杂度 O(1) 的解法。如果数字范围不是 0 到 n-1，那原地交换的思路就完全不成立了。
注意：题目说"找出任意一个重复的数字"就够了，不需要找出所有重复的数字，也不需要统计重复次数。这个细节很重要，它意味着你不需要完整遍历整个数组，找到就可以直接返回。
2.2 思路一：排序后相邻比较
最直观的做法是什么？排序。排完之后，重复的数字一定相邻，扫一遍就行了。
def find_duplicate_sort(nums): nums.sort() for i in range(1, len(nums)): if nums[i] == nums[i - 1]: return nums[i] return -1这个解法的时间复杂度是 O(n log n)，空间复杂度取决于排序算法，Python 的 sort 是 Timsort，最坏情况需要 O(n) 的额外空间。
优点是简单，不容易写错。缺点是时间复杂度不够好，而且会修改原数组。如果面试官问你"能不能不修改原数组"，这个解法就直接出局了。
2.3 思路二：哈希表记录出现次数
第二个想到的肯定是哈希表。遍历数组，用一个集合记录已经出现过的数字，如果当前数字已经在集合里了，直接返回。
def find_duplicate_hash(nums): seen = set() for num in nums: if num in seen: return num seen.add(num) return -1时间复杂度 O(n)，空间复杂度 O(n)。这是最通用的解法，不管数字范围是多少都能用。但问题也很明显：需要额外的 O(n) 空间。如果面试官说"空间复杂度能不能降到 O(1)"，你就得换思路了。
2.4 思路三：原地交换，下标映射法
这才是这道题的精髓所在。
核心思想是这样的：因为数字范围是 0 到 n-1，所以如果没有重复数字，每个数字 i 应该正好放在下标 i 的位置上。也就是说，nums[i] == i 应该对所有 i 成立。
那如果有重复数字呢？说明某个位置上的数字不对，而另一个数字占了两个位置。我们可以通过不断交换，把每个数字放到它"应该在"的位置上。交换过程中如果发现目标位置上已经有了正确的数字，那就找到了重复。
具体流程是这样的：
- 从下标 0 开始遍历。
- 如果 nums[i] == i，说明这个位置已经对了，跳过。
- 如果 nums[i] != i，检查 nums[nums[i]] 是否等于 nums[i]。
- 如果相等，说明 nums[i] 这个数字在它应该在的位置上已经有一个了，找到了重复，直接返回。
- 如果不等，交换 nums[i] 和 nums[nums[i]]，把 nums[i] 放到正确的位置上。
- 交换后继续在当前下标检查（因为换过来的新数字可能也不对）。
def find_duplicate_swap(nums): i = 0 while i < len(nums): if nums[i] == i: i += 1 continue if nums[nums[i]] == nums[i]: return nums[i] # 交换 nums[nums[i]], nums[i] = nums[i], nums[nums[i]] return -1这个解法的时间复杂度是 O(n)。虽然有一个 while 循环里面套了交换操作，但每个数字最多被交换两次就能放到正确的位置上，所以总的交换次数是 O(n) 的。空间复杂度是 O(1)，完全原地操作。
实操心得：写交换的时候一定要注意顺序。
nums[nums[i]], nums[i] = nums[i], nums[nums[i]]这个写法在 Python 里是对的，因为右边先求值。但在 C++ 或 Java 里，你得用临时变量，否则会出错。我见过太多人在这里翻车。
2.5 二分查找的思路：不修改数组的 O(1) 空间解法
如果面试官加一个条件："不能修改原数组，且空间复杂度 O(1)"，那原地交换就不能用了。这时候可以用二分查找的思路。
思路是这样的：数字范围是 0 到 n-1，我们可以统计数组中落在某个区间 [left, right] 内的数字个数。如果个数大于区间长度，说明重复数字在这个区间内。然后缩小范围继续找。
def find_duplicate_binary(nums): left, right = 0, len(nums) - 1 while left < right: mid = (left + right) // 2 count = sum(1 for num in nums if left <= num <= mid) if count > mid - left + 1: right = mid else: left = mid + 1 return left时间复杂度是 O(n log n)，因为每次统计需要遍历整个数组，二分需要 log n 次。空间复杂度 O(1)。这个解法不修改原数组，但时间上比原地交换慢一些。
注意：二分查找解法有一个前提，就是数字范围必须是 0 到 n-1。如果范围变了，这个解法就不适用了。而且这个解法只能找到一个重复数字，不能保证找到所有。
2.6 三种解法的对比与选择
| 解法 | 时间复杂度 | 空间复杂度 | 是否修改原数组 | 适用场景 |
|---|---|---|---|---|
| 排序 | O(n log n) | O(n) | 是 | 快速实现，不要求最优 |
| 哈希表 | O(n) | O(n) | 否 | 通用，数字范围无限制 |
| 原地交换 | O(n) | O(1) | 是 | 数字范围 0~n-1，允许修改 |
| 二分查找 | O(n log n) | O(1) | 否 | 不允许修改数组，范围 0~n-1 |
实际面试中，我一般会先写哈希表解法，保证正确性，然后根据面试官的追问逐步优化。如果面试官直接问"能不能 O(1) 空间"，那就上原地交换。如果再加"不能修改数组"，那就上二分。
3. 二维数组中的查找：有序性带来的降维打击
3.1 题目描述与关键条件
题目是这样的：在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
举个例子：
1 2 8 9 2 4 9 12 4 7 10 13 6 8 11 15查找 7 返回 true，查找 5 返回 false。
这道题的关键在于每一行从左到右递增，每一列从上到下递增。注意，不是整个二维数组全局有序，而是行和列分别有序。这个条件比全局有序弱，但比完全无序强得多。
很多人第一反应是逐行二分查找。每一行都是有序的，对每一行做二分，时间复杂度是 O(m log n)，其中 m 是行数，n 是列数。这个解法不算差，但还不是最优的。
3.2 暴力遍历与逐行二分
暴力遍历就是两层循环，时间复杂度 O(mn)，基本不用考虑，除非数组特别小。
逐行二分稍微好一点：
def search_matrix_binary(matrix, target): for row in matrix: left, right = 0, len(row) - 1 while left <= right: mid = (left + right) // 2 if row[mid] == target: return True elif row[mid] < target: left = mid + 1 else: right = mid - 1 return False时间复杂度 O(m log n)，空间复杂度 O(1)。这个解法利用了行的有序性，但没有利用列的有序性。如果面试官追问"能不能利用列也有序这个条件"，你就需要换思路了。
3.3 右上角起始的线性查找
这是这道题的最优解，也是最能体现"有序性利用"精髓的解法。
核心思想是：从右上角开始查找。为什么是右上角？因为右上角这个位置很特殊——它是当前行的最大值，同时是当前列的最小值。
具体流程：
- 从右上角 (0, n-1) 开始。
- 如果当前元素等于目标值，返回 true。
- 如果当前元素大于目标值，说明目标值不可能在这一列（因为这一列从上到下递增，当前元素已经是这一列最小的了，下面的只会更大），所以向左移动一列。
- 如果当前元素小于目标值，说明目标值不可能在这一行（因为这一行从左到右递增，当前元素已经是这一行最大的了，左边的只会更小），所以向下移动一行。
- 重复直到越界，返回 false。
def search_matrix(matrix, target): if not matrix or not matrix[0]: return False rows, cols = len(matrix), len(matrix[0]) row, col = 0, cols - 1 while row < rows and col >= 0: if matrix[row][col] == target: return True elif matrix[row][col] > target: col -= 1 else: row += 1 return False时间复杂度是 O(m + n)，因为每次要么向左一列，要么向下一行，最多走 m + n 步。空间复杂度 O(1)。这个解法同时利用了行和列的有序性，是最优解。
实操心得：为什么选右上角而不是左下角？其实左下角也可以，思路完全对称。左下角是当前行的最小值，当前列的最大值。如果当前元素大于目标值，向上移动；如果小于目标值，向右移动。但右上角更符合直觉，因为"从大到小排除列，从小到大排除行"这个逻辑比较顺。
3.4 为什么不能从左上角或右下角开始
这个问题我被问过好几次。从左上角开始，当前元素是全局最小值。如果目标值比它大，你既不能排除行也不能排除列，因为右边和下边都可能包含目标值。这就退化成暴力搜索了。
右下角同理，当前元素是全局最大值。如果目标值比它小，你既不能排除行也不能排除列，因为左边和上边都可能包含目标值。
所以关键点是：起始位置必须能够让你在每次比较后，明确排除一行或一列。右上角和左下角满足这个条件，左上角和右下角不满足。
3.5 边界条件与特殊输入处理
这道题有几个容易翻车的边界条件：
- 矩阵为空：
matrix = []，直接返回 false。 - 矩阵只有一行或一列：逻辑仍然成立，但要注意行列索引不要越界。
- 矩阵中所有元素相同：如果目标值等于这个元素，返回 true；否则在右上角比较后就会一直移动直到越界。
- 目标值比矩阵中所有元素都小或都大：会一直移动直到越界，返回 false。
# 边界测试用例 assert search_matrix([], 5) == False assert search_matrix([[]], 5) == False assert search_matrix([[1]], 1) == True assert search_matrix([[1]], 2) == False assert search_matrix([[1, 2, 3]], 2) == True assert search_matrix([[1], [2], [3]], 2) == True注意：Python 中
if not matrix or not matrix[0]这个判断很关键。如果只写if not matrix，当 matrix 是[[]]的时候会通过检查，然后在len(matrix[0])那里报 IndexError。我踩过这个坑，排查了半天才发现是空行的问题。
4. 两道题的共通思维：有序性与下标映射
4.1 下标映射的本质
"找出数组中重复的数"的原地交换解法，本质上是利用了数字与下标的一一对应关系。因为数字范围是 0 到 n-1，所以每个数字都有一个"应该在"的位置。通过交换把数字放到正确的位置上，就能在 O(n) 时间内找到重复。
这种思路在很多数组类问题中都有应用。比如"缺失的第一个正数"、"找到所有数组中消失的数字"等，都是利用下标映射来做到 O(1) 空间。
核心条件是：元素的取值范围和数组长度有明确的对应关系。如果这个条件不满足，下标映射就用不了。
4.2 有序性利用的通用套路
"二维数组中的查找"利用的是行和列分别有序这个条件。通过从右上角开始，每次比较都能排除一行或一列，把 O(mn) 的暴力搜索降到 O(m+n)。
有序性利用的通用套路是：找到一个起始点，使得每次比较后能排除一部分搜索空间。一维有序数组的二分查找是这个套路的最简单形式，二维有序矩阵的右上角查找是它的二维扩展。
类似的题目还有"搜索旋转排序数组"、"寻找峰值"等，都是利用局部有序性来缩小搜索范围。
4.3 空间换时间的取舍
这两道题都涉及一个核心取舍：要不要用额外空间来换时间。
哈希表解法用 O(n) 空间换 O(n) 时间，原地交换用 O(1) 空间但也做到了 O(n) 时间。二分查找用 O(1) 空间但时间是 O(n log n)。
实际做题时，我一般会先问清楚约束条件：能不能修改原数组？空间复杂度有没有要求？时间复杂度有没有要求？根据这些条件来选择最合适的解法。
实操心得：面试的时候，不要一上来就写最优解。先写一个能跑的暴力解，然后逐步优化。这样既能保证有东西可写，又能展示你的思考过程。面试官更看重的是你的思路，而不是你能不能背出最优解的代码。
5. 常见问题与排查技巧实录
5.1 原地交换法为什么会死循环
原地交换法最容易出的问题就是死循环。我一开始写的时候，交换完之后没有正确处理当前下标，导致一直在同一个位置打转。
问题出在这里：交换之后，当前位置的数字变了，但你可能还需要继续检查这个位置。如果你直接i += 1，就会漏掉一些情况。
正确的做法是：交换之后不移动 i，继续在当前下标检查。只有当nums[i] == i的时候才移动 i。
# 错误写法：交换后直接 i += 1 while i < len(nums): if nums[i] != i: nums[nums[i]], nums[i] = nums[i], nums[nums[i]] i += 1 # 这里可能跳过需要检查的位置 # 正确写法：交换后不移动 i while i < len(nums): if nums[i] == i: i += 1 elif nums[nums[i]] == nums[i]: return nums[i] else: nums[nums[i]], nums[i] = nums[i], nums[nums[i]]5.2 二维数组查找的越界问题
二维数组查找最常见的 bug 是数组越界。尤其是在矩阵为空、只有一行、只有一列的情况下，很容易出现 IndexError。
排查的时候，我一般会先加边界检查，然后用小规模的测试用例逐步验证。比如先用 1x1 的矩阵测试，再用 1xN 和 Nx1 的矩阵测试，最后用完整的矩阵测试。
| 问题现象 | 可能原因 | 排查方法 |
|---|---|---|
| IndexError | 矩阵为空或空行 | 检查not matrix or not matrix[0] |
| 结果错误 | 行列索引搞反了 | 打印每次移动后的 row 和 col |
| 死循环 | 移动方向搞反了 | 检查大于和小于时的移动逻辑 |
| 漏解 | 起始位置选错了 | 确认从右上角或左下角开始 |
5.3 二分查找的边界处理
二分查找的边界处理是出了名的容易出错。left <= right还是left < right？mid + 1还是mid？这些细节稍不注意就会导致死循环或漏解。
我的经验是：统一使用左闭右闭区间，即left <= right，right = mid - 1，left = mid + 1。这样不容易出错。
# 左闭右闭的标准写法 left, right = 0, len(nums) - 1 while left <= right: mid = (left + right) // 2 if nums[mid] == target: return mid elif nums[mid] < target: left = mid + 1 else: right = mid - 1 return -1注意：
mid = (left + right) // 2在 Python 中不会溢出，但在 C++ 或 Java 中，如果 left 和 right 都很大，可能会溢出。安全的写法是mid = left + (right - left) // 2。
5.4 面试中的追问与应对
这两道题在面试中经常会有追问。我整理了一些常见的追问和应对思路：
追问一：如果数组中有多个重复数字，怎么找出所有？
对于"找出数组中重复的数"，如果需要找出所有重复数字，哈希表解法最直接。原地交换法也可以，但需要额外处理，因为找到一个重复后不能直接返回，要继续扫描。
追问二：如果数字范围不是 0 到 n-1 呢？
那原地交换和二分查找都不能用了，只能用哈希表或排序。这也是为什么面试官会先给出数字范围这个条件——它决定了你能用哪些解法。
追问三：二维数组如果行和列不是分别有序，而是全局有序呢？
如果整个二维数组全局有序（按行展开后是一个有序一维数组），那可以直接把二维数组当作一维数组做二分查找，时间复杂度 O(log(mn))。
追问四：如果二维数组的行数和列数非常大，内存放不下怎么办？
这是一个系统设计类的问题。可以考虑分块读取，或者用外部排序的思路。不过一般面试中不会问到这么深，除非是专门考系统设计的岗位。
6. 从刷题到实战：这些思路还能用在哪
6.1 数据去重与重复检测
"找出数组中重复的数"的思路在实际工作中非常常见。比如日志分析中检测重复请求、数据清洗中找出重复记录、用户行为分析中识别异常重复操作等。
哈希表解法是最通用的，适合大多数场景。如果数据量特别大，内存放不下，可以考虑用布隆过滤器做初步筛选，或者用外部排序后相邻比较。
原地交换法的思路在特定场景下也很有用。比如数据本身就是按某种规则编号的，你可以利用编号和存储位置的对应关系来快速检测重复。
6.2 有序矩阵的快速检索
"二维数组中的查找"的思路在数据库索引、图像处理、游戏地图寻路等场景中都有应用。
比如在一个按行按列都有序的评分矩阵中查找某个分数，或者在一个按时间和优先级排序的任务队列中查找特定任务，都可以用类似的思路。
核心思想是：利用数据的局部有序性，每次比较排除一部分搜索空间。这个思想不仅适用于二维数组，也适用于更高维度的有序结构。
6.3 算法思维的迁移
这两道题教给我们的不只是具体的解法，更是一种思维方式：
- 观察数据特征：数字范围、有序性、重复性，这些特征决定了你能用什么算法。
- 权衡时空复杂度：没有绝对最优的解法，只有最适合当前约束的解法。
- 从暴力到最优：先写出能跑的解法，再逐步优化，这是解决所有算法问题的通用路径。
我在实际工作中遇到性能问题时，经常会回想这两道题的思路。比如一个查询很慢，我会先想：数据有没有有序性可以利用？能不能用空间换时间？能不能通过某种映射关系把 O(n) 降到 O(1)？
这些思维方式，比具体的代码更有价值。代码会过时，但思考问题的方式不会。
最后分享一个我刷题时的小习惯：每做完一道题，我会问自己三个问题——这道题的核心条件是什么？如果条件变了，解法要怎么调整？这道题的思路还能用在哪些地方？这三个问题能帮我把一道题吃透，而不是做完就忘。
