1. 从两道题看算法面试的底层逻辑找出数组中重复的数和二维数组中的查找这两道题放在一起看特别有意思。它们表面上一个是关于一维数组的去重与计数另一个是关于二维矩阵的搜索剪枝但骨子里考的是同一件事——你能否在有限的空间和时间内把数据的结构特征吃透然后选择最合适的策略去逼近答案。我这些年带过不少刚入行的朋友也帮人做过模拟面试发现一个很普遍的现象很多人拿到题就开始写循环写完发现超时或者空间爆了再回头改。这种先写后想的习惯在简单题上还能蒙混过关一旦遇到有约束条件的题基本就废了。这两道题恰好是训练先分析、再动手的绝佳素材。先说清楚这两道题各自是什么、能解决什么问题、适合谁来啃。第一题找出数组中重复的数通常的设定是一个长度为 n 的数组里面的元素取值范围是 0 到 n-1也就是说理论上每个位置都该放一个不重复的数但实际有数字重复了要求你找出任意一个重复的数。第二题二维数组中的查找经典设定是一个二维矩阵每一行从左到右递增每一列从上到下递增给一个目标值判断它是否存在于矩阵中。这两道题适合谁适合所有正在准备技术面试的人适合想补一补算法基本功的开发者也适合那些能写业务代码但一遇到算法就发怵的朋友。它们不需要高深的数学但能把你的思维习惯暴露得干干净净。接下来我会把这两道题从思路设计、细节实现、踩坑经验到扩展变体一层一层拆开讲尽量让你看完就能自己复现并且知道每一步为什么这么做。2. 找出数组中重复的数思路拆解与方案选型2.1 先搞清楚题目到底在约束什么很多人一看到找重复的数脑子里第一反应是搞个哈希表遍历一遍遇到已经存在的就返回。这个思路没错时间复杂度 O(n)写起来也快。但问题在于面试官往往会在你写完哈希表之后补一句能不能不用额外的空间这时候如果你没有准备就很容易卡住。所以第一步必须把题目的约束条件读透。典型的完整描述是这样的数组长度为 n1所有元素的值都在 1 到 n 之间所以根据抽屉原理至少有一个数字是重复的。要求找出任意一个重复的数字并且不能修改原数组有些版本允许修改有些不允许这个区别很关键。这里有几个隐藏信息需要挖出来。第一值在 1 到 n 之间这个条件极其重要它意味着数组里的每个值都可以当作下标来用这是后面原地交换和二分计数两种解法的根基。第二不能修改原数组这个限制直接排除了原地交换法逼着你去想别的办法。第三找出任意一个而不是找出所有说明你不需要完整统计只要逮住一个就行这给了优化空间。我见过太多人因为没读清楚值域这个条件上来就写了个通用去重结果面试官一问如果值域是 0 到 10 的 9 次方呢整个人就懵了。所以读题这个环节值得你花两分钟把每个数字、每个范围都圈出来。2.2 四种解法横向对比从暴力到最优这道题我一共整理出四种主流解法它们分别对应不同的约束组合我列个表让你一眼看清差异。解法时间复杂度空间复杂度是否修改原数组适用场景排序后相邻比较O(n log n)O(1) 或 O(n)取决于排序实现允许修改、对时间不敏感哈希表计数O(n)O(n)否允许额外空间、追求速度原地交换归位O(n)O(1)是允许修改、要求常数空间二分计数O(n log n)O(1)否不允许修改、要求常数空间排序法的逻辑最直白排完序重复的数一定相邻扫一遍就行。但它的问题是时间复杂度上去了而且如果要求不修改原数组你还得先复制一份空间又变成 O(n)。所以排序法一般只作为兜底方案提一句不作为主推。哈希表法是大多数人的第一反应写起来最顺手。用一个集合或者计数数组遍历时判断是否出现过。它的优势是逻辑简单、不易出错缺点是空间 O(n)。在面试里如果你时间紧张先把哈希表写出来保证能跑然后再优化这是很稳妥的策略。原地交换法是这道题的精髓所在。核心思想是既然值都在 1 到 n 之间那理想情况下数字 i 应该待在下标 i 的位置上。我们从左到右扫描对于当前位置 i如果 nums[i] 不等于 i就看看 nums[i] 这个值应该去的位置上是不是已经是它了如果是说明找到了重复如果不是就交换过去。这个过程每个元素最多被交换两次所以整体是 O(n)。二分计数法是最容易被忽略但面试官最爱考的。它的思路是在 1 到 n 这个值域上做二分对于中点 mid统计数组中小于等于 mid 的元素个数。如果这个个数大于 mid说明重复的数在 1 到 mid 之间否则在 mid1 到 n 之间。每次统计要遍历一遍数组二分要 log n 次所以是 O(n log n)空间 O(1)而且不修改原数组。2.3 为什么二分计数法值得你多花十分钟搞懂我特别想强调二分计数法因为它是这四种解法里思维含量最高的也是最能体现你对值域二分这个技巧理解的。很多人第一次看到这个解法会觉得很绕明明是在数组里找重复怎么跑到值域上去二分了这里的关键洞察是重复意味着拥挤。假设值域是 1 到 n正常情况下小于等于 mid 的数最多有 mid 个就是 1、2、3 一直到 mid。但如果实际统计出来超过了 mid 个那就说明在 1 到 mid 这个区间里有数字被重复放置了。这个逻辑用抽屉原理一解释就通了mid 个抽屉你塞了超过 mid 个东西必然有抽屉里不止一个。这个思路的价值在于它把找重复这个问题转化成了找拥挤区间而找拥挤区间天然适合二分。你不需要知道具体是哪个数重复只需要不断缩小范围最后范围缩到一个数那个数就是答案。这种不直接找答案而是通过排除法逼近答案的思维方式在很多难题里都会用到。我个人的建议是哈希表法和原地交换法必须熟练到能默写二分计数法要理解透彻能讲清楚原理。这三板斧在手无论面试官怎么加约束你都能接得住。3. 二维数组中的查找从暴力到优雅剪枝3.1 题目特征分析有序性到底给了什么二维数组查找这道题题目描述通常是这样给定一个 m 行 n 列的二维数组每一行从左到右递增每一列从上到下递增。给一个目标值 target判断它是否在数组中。新手最容易犯的错是把每行递增、每列递增理解成整个数组完全有序。这两者差别巨大。完全有序的话你可以直接把它拉平成一维数组做二分O(log(mn)) 就搞定了。但实际上每行递增加每列递增并不能保证拉平后有序。举个例子1 2 8 9 2 4 9 12 4 7 10 13 6 8 11 15你看第一行最后是 9第二行开头是 2拉平后 9 后面跟着 2明显不是有序的。所以不能简单拉平二分。那这个有序性到底给了什么它给了你方向性。在任意一个位置 (i, j)如果 target 比当前元素大那么 target 可能在右边也可能在下边如果 target 比当前元素小可能在左边也可能在上边。这种两个方向都有可能的情况就是这道题的难点所在。你需要找到一个特殊的起点让每次比较都能排除掉一整行或一整列把不确定性降到只有一个方向。3.2 右上角起点法为什么它是最优解这道题的标准最优解是从右上角或者左下角开始搜索。我以右上角为例讲清楚原理。假设我们从右上角 (0, n-1) 出发。这个位置有个绝妙的性质它是它所在行的最大值同时是它所在列的最小值。这句话是理解整个算法的钥匙。现在拿 target 和当前元素比较如果 target 等于当前元素找到了返回。如果 target 小于当前元素因为当前元素是所在列的最小值所以这一列从当前位置往下所有元素都大于当前元素也就都大于 target。既然这一列下面的都比 target 大那 target 不可能在这一列里直接排除整列往左移动一列。如果 target 大于当前元素因为当前元素是所在行的最大值所以这一行从当前位置往左所有元素都小于当前元素也就都小于 target。既然这一行左边的都比 target 小那 target 不可能在这一行里直接排除整行往下移动一行。每一步要么排除一行要么排除一列最多走 mn 步就能确定答案。时间复杂度 O(mn)空间 O(1)。这个复杂度已经是最优的了因为最坏情况下你确实需要检查这么多元素。左下角起点是对称的它是所在行的最小值、所在列的最大值。逻辑完全一样只是移动方向反过来。我个人更习惯右上角因为往左往下这个方向感比较顺。3.3 为什么不能从左上角或右下角开始这个问题我被问过很多次值得单独说清楚。假设你从左上角 (0, 0) 开始这个位置是整行的最小值和整列的最小值。如果 target 大于当前元素target 可能在右边也可能在下边你没法排除任何一个方向。如果 target 小于当前元素那直接说明 target 不存在因为左上角已经是最小值了这种情况倒是好处理。问题就出在target 更大的时候你陷入了两难。右下角同理它是整行的最大值和整列的最大值。target 小于它时可能在左边也可能在上边又是两难。所以起点选择的本质是找到一个位置使得比较结果能唯一确定搜索方向。右上角和左下角满足这个条件左上角和右下角不满足。这个分析过程比记住结论重要得多因为面试官很可能追问为什么你答得出原理才算是真懂了。4. 两道题的代码实现与关键细节4.1 找出重复数的三种实现先看哈希表法这是最直观的版本def find_duplicate_hash(nums): seen set() for num in nums: if num in seen: return num seen.add(num) return -1这段代码没什么好说的注意边界情况如果数组为空或者没有重复返回 -1 表示未找到。实际面试时最好先问清楚如果不存在重复怎么办别自己假设。再看原地交换法这个需要小心处理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[i] 和 nums[nums[i]] nums[nums[i]], nums[i] nums[i], nums[nums[i]] return -1这里有个 Python 的坑要注意nums[nums[i]], nums[i] nums[i], nums[nums[i]]这种多重赋值Python 会先计算右边所有表达式的值再依次赋值给左边。所以右边第二个nums[nums[i]]用的是交换前的nums[i]这是对的。但如果你写成先赋值再交换就会出错。我建议初学者还是老老实实用临时变量可读性更好temp nums[i] nums[i] nums[temp] nums[temp] temp最后看二分计数法def find_duplicate_binary(nums): left, right 1, 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注意这里的计数范围是left num mid区间长度是mid - left 1。如果统计个数超过区间长度说明重复在左半边。这个细节很容易写错我第一次写的时候就因为区间长度算错导致死循环。4.2 二维数组查找的实现与边界处理右上角起点法的代码很简洁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这段代码有几个边界必须处理。第一矩阵可能为空matrix是空列表或者matrix[0]是空列表这两种情况都要提前返回 False否则后面取matrix[0]会报错。第二循环条件是row rows and col 0两个条件缺一不可因为 row 只会增加col 只会减少任何一个越界都要停。第三返回 False 的位置在循环外面说明走完了所有可能都没找到。我见过有人把col 0写成col 0结果漏掉了第 0 列这种错误在测试用例刚好落在第 0 列时才会暴露非常隐蔽。所以写完代码一定要手动跑几个边界用例target 在第一行、target 在最后一列、target 比所有元素都小、target 比所有元素都大。4.3 两道题的空间复杂度陷阱这两道题在空间复杂度上都有陷阱我单独拎出来说。找重复数这道题如果你用哈希表空间是 O(n)。面试官如果要求 O(1)你就得换原地交换或二分计数。但原地交换会修改原数组如果题目明确说不能改你就只能用二分计数。所以空间复杂度的选择是跟能否修改原数组这个约束绑定的不能孤立地看。二维数组查找这道题空间复杂度看起来是 O(1)因为你只用了 row 和 col 两个变量。但如果你不小心在函数里复制了矩阵或者用了递归空间就上去了。我见过有人用递归写这个搜索每次递归传递子矩阵的切片结果空间变成 O(mn)完全没必要。迭代写法又简单又省空间没有理由用递归。5. 常见问题与排查技巧实录5.1 找重复数的高频翻车点问题一原地交换法死循环。这是最常见的。原因通常是交换逻辑写错导致两个位置的值来回换但始终不满足终止条件。排查方法在循环里打印 i 和 nums[i]看它是不是在某个状态卡住了。正常情况下每次交换都会让至少一个元素归位如果发现交换后状态没变化就是交换写反了。问题二二分计数法的区间算错。典型症状是死循环或者返回错误答案。核心检查点有两个计数区间是[left, mid]还是[left, mid)区间长度是mid - left 1还是mid - left。这两个必须匹配计数区间包含 mid长度就要加一。我建议在纸上画一个具体的小例子比如 left1, right3, mid2手动数一遍确认逻辑对得上。问题三哈希表法遇到值域很大的情况。如果题目没说值域是 1 到 n而是任意整数那哈希表法依然可用但原地交换和二分计数就失效了因为它们依赖值域和下标的一一对应关系。所以拿到题先确认值域这决定了你能用哪些解法。5.2 二维查找的典型错误错误一起点选错。从左上角或右下角开始然后发现逻辑走不通又改来改去。记住结论只能从右上角或左下角开始。如果你不确定就在纸上画一个 3x3 的矩阵手动模拟一下从左上角开始的过程你会立刻发现两难困境。错误二移动方向搞反。从右上角开始时target 小于当前元素应该往左移col 减一target 大于当前元素应该往下移row 加一。这两个方向很容易记混。我的记忆口诀是小了往左大了往下因为右上角往左是变小往下是变大跟 target 的大小关系一致。错误三循环条件写漏。前面提过row rows and col 0两个条件都要有。我建议写成 while 循环后在脑子里过一遍如果 target 比所有元素都大row 会一直加到 rows此时循环应该退出如果 target 比所有元素都小col 会一直减到 -1循环也应该退出。两个方向都验证一遍就不会漏。5.3 面试现场的时间分配建议这两道题如果出现在同一场面试里通常是作为热身题或者中等题出现的。我的建议是找重复数控制在 10 分钟内二维查找控制在 8 分钟内。具体分配是读题和确认约束 2 分钟讲思路 2 分钟写代码 4 分钟测试边界 2 分钟。如果面试官在你写完哈希表后追问能不能优化空间不要慌直接说可以用原地交换法但会修改原数组如果要求不修改可以用二分计数法时间会变成 O(n log n)。把权衡讲清楚比闷头写代码更加分。6. 从这两道题延伸出的通用解题框架6.1 遇到数组题先问自己三个问题我总结了一个适用于大多数数组类题目的思考框架这两道题都能套进去。第一个问题数组的值域和下标有没有关系如果值域是 0 到 n-1 或者 1 到 n那下标就可以当索引来用原地交换、计数排序这类技巧就有了用武之地。找重复数这道题就是典型。第二个问题数组有没有序有序性能不能利用如果有序二分就是首选。二维查找这道题的有序性是二维的所以不能直接二分但可以利用有序性做方向性剪枝。第三个问题能不能用空间换时间或者用时间换空间哈希表是空间换时间二分计数是时间换空间。面试时先问清楚约束再决定往哪个方向优化。这三个问题问下来大部分数组题的思路就清晰了。6.2 二维问题的降维思路二维数组查找这道题本质上是一个降维的过程。你从右上角出发每次比较都能把问题从 m 行 n 列缩小到 m 行 n-1 列或者 m-1 行 n 列也就是每次砍掉一行或一列。这种每步排除一个维度的思路在二维问题里非常常见。类似的还有搜索二维矩阵的变体比如矩阵每行有序但行之间无序那就得每行单独二分。再比如矩阵是螺旋有序的那就得用别的方法。核心都是先分析有序性的具体形式再决定剪枝策略。6.3 边界测试用例清单无论哪道题写完代码后我都会跑这几个用例对于找重复数数组长度为 2两个元素相同重复元素在开头重复元素在结尾有多个重复元素返回任意一个即可数组长度为 1虽然按题意不会出现但防御性测试对于二维查找空矩阵单元素矩阵target 等于它和不等于它target 在第一行target 在最后一列target 比最小值还小target 比最大值还大target 在矩阵中间这些用例覆盖了绝大多数边界跑一遍没问题基本就能放心提交了。7. 我个人在实际操作中的几点体会这两道题我前前后后给不同的人讲过不下几十遍最大的感受是很多人不是不会写代码而是不会分析问题。他们拿到题就想套模板看到数组就想排序看到查找就想二分但没想过这个数组有什么特殊性质这个查找有什么特殊约束。找重复数这道题教会我的是约束条件不是限制而是线索。值在 1 到 n 之间这个条件在不会用的人眼里是废话在会用的人眼里是通往 O(1) 空间的钥匙。二维查找教会我的是起点的选择决定了问题的难度。同样一个矩阵从左上角开始是死路从右上角开始就是坦途。这种换个角度看问题的能力比记住多少种解法都重要。最后分享一个小技巧如果你在面试中一时想不出最优解先把暴力解写出来然后问面试官我可以先写一个能跑的版本再优化吗。大多数面试官都会同意而且你写暴力的过程中往往就能发现优化的方向。最怕的是卡在那里不动时间白白流逝。先跑起来再跑得快这个顺序不能反。