LeetCode高频题：2N数组中找重复N次元素的O(1)空间解法

如果让你在一分钟内说出一个长度为 2N 的数组里找出重复 N 次元素的做法，你会先想到什么？很多人第一反应是哈希表计数，少部分人会想排序，但真正卡住大多数人的，是“为什么 O(1) 空间也能做”。这道题表面是个计数题，实际上考的是你对数组长度和出现次数之间比例关系的敏感度——目标元素恰好占了一半，这是整道题唯一的突破口。今天把这道经典题的题意拆解、数学证明、三种解法和面试常见坑一次讲透。

先对齐一下标准题意：数组长度是 2N，里面一共包含 N+1 种不同的元素，其中一个元素恰好重复出现 N 次，剩下 N 个元素各出现一次，要你把这个重复元素找出来。注意“其余元素各出现一次”这个条件，它决定了后面很多解法的正确性，也决定了最优解的存在性。如果你只知道“有个元素出现了 N 次”，其他元素可能乱重复，题目性质就完全变了，这个放到最后讲。

1. 先抓住题目的隐藏结构：一半占比带来的三个推论

1.1 标准题意到底是什么

很多人刷到这题会习惯性打开计数器，这没错，但“用哈希表硬解”属于最没区分度的答案。真正值得琢磨的是：为什么数组长度偏偏是 2N，而不是 3N、4N？

因为 2N 这个长度有一个很特殊的含义——目标元素出现 N 次，占总数的一半，剩下 N 个位置由 N 个互不相同的元素瓜分。换句话说，数组里除了目标元素是“双份”以外，其余全是“单份”，它是唯一一个多出来的。这个理解非常直观，而且能直接推出一个重要结论：其他元素之间互相都不相等，两个不同的非目标元素永远不会相邻重复。

这里有个容易忽略的点：题目说“包含 N+1 种不同的元素”，意味着你来数组里最多只能见到 N+1 个不同的值，其中 N 个出现一次，1 个出现 N 次。所以数组中任何一对相等的元素，必然跟目标元素有关。这句话是哈希表法正确性的根基，也是唯一能保证间隔法正确性的关键条件。我在面试模拟的时候发现，能把这句话主动说出来的候选人，基本就掌握了这道题的题眼。

1.2 从“占一半”能立刻推出的三件事

第一件事：任意随机抽两个位置，抽到两个目标元素的概率不是零，在 N 很大时大约接近四分之一。这个概率看起来不够高，但它意味着“随机化检查”这条路存在，不过我们后面会用确定性解法，不用赌概率。

第二件事：排序之后，目标元素必然形成一个长度为 N 的“连续块”。因为目标元素出现 N 次，排序后必然聚在一起，其他 N 个唯一元素分布在它两侧。这给了排序法一个很好的切入点：你根本不需要在排序数组里全盘扫描，只需要看中间附近的位置就够了。

第三件事，也是最重要的一件事：目标元素在原始数组中的位置不可能太分散。N 个相同的元素要塞进 2N 个位置，如果彼此离得太远，根本放不下。于是“必有两个目标元素靠得很近”这个事实，就成了 O(1) 空间线性时间解法的直接依据。下一节我们把这件事用数学证明讲透。

2. 核心定理：为什么两个目标元素一定靠得很近

2.1 反证法的完整推导

我直接给出结论：在满足题意的数组里，必存在两个目标元素，它们在原数组中的下标差不超过 3。

证明用反证。假设这在任何一对目标元素上都不成立，也就是说任意两个目标元素的下标差都至少是 4。现在把目标元素在数组中的下标从小到大记为 p1、p2、……、pN，因为任意相邻出现位置的距离至少是 4，所以最后一个目标元素的位置至少是 p1 + 4(N-1)。p1 不可能小于 0，所以最后一个目标元素的下标至少是 4(N-1)。

但数组长度总共是 2N，最后一个下标最大只有 2N-1。想让这些目标元素全放进去，必须先满足：

4(N-1) ≤ 2N-1

化简一下：4N - 4 ≤ 2N - 1，得到 2N ≤ 3，也就是 N ≤ 1。可题目里目标元素要重复 N 次，N 至少是 2，否则“重复 N 次”根本没意义。于是矛盾。

所以必然存在两个目标元素的下标差不超过 3。这个证明的本质是空间不够：你要往 2N 个格子里塞 N 个相同的值，如果每两个之间都隔着至少 3 个其他元素，格子的数量根本扛不住。用生活化的话说，就像一辆满载的公交车上，坐同一站下车的乘客不可能全都隔得远远的，总有人挨在一起。

2.2 为什么是 3，而不是 2 或 4

不少人会问：既然目标元素占一半，为什么不能直接说“必有相邻的两个目标元素”？这不是因为你运气差，而是真的存在反例。

考虑 N=2 的情况，数组 [1,2,3,1]，目标 1 出现在首尾两个位置，下标差正好是 3，并不存在相邻的两个 1。所以“下标差不超过 2”这个结论在 N=2 时不成立。但如果把阈值放宽到 3，就覆盖了所有 N≥2 的情况。

再想想为什么不用更宽松的 4？当然，下标差不超过 4 也必成立，但阈值越小，代码里要检查的距离越短，实现越简单。检查距离 1、2、3 已经足够覆盖所有情况了，没必要额外多看一个位置。所以 3 是最优平衡点。

这个证明推导出来之后，最优解就变成了一个非常朴素的操作：从前往后扫描，每到一个位置，就看看它后面第 1、第 2、第 3 个位置上的值跟自己是否相等，一旦遇到相等的，直接返回。因为根据定理，你迟早会碰到一对目标元素。

3. 三类解法横向拆解：哈希、排序、间隔法

3.1 哈希表法：先答这个，保证不冷场

这道题最直接的解法就是维护一个集合，遍历数组时把每个元素丢进去，一旦发现某个元素已经在集合里，它就是答案。

def repeatedNTimes(nums): seen = set() for x in nums: if x in seen: return x seen.add(x)

为什么第一次遇到重复就是答案？因为题目保证了其他 N 个元素各出现一次，互相之间不可能重复，只有目标元素会出现第二次。所以集合里一旦出现碰撞，碰撞的元素必然是目标。

这个解法的优点是几乎不需要证明，不容易写错，面试时先抛出来拿个基础分。缺点是空间复杂度是 O(N)，面试官十有八九会追问一句“能不能把空间降到 O(1)”。这时候你再亮出间隔法，节奏就很自然。

3.2 排序法：代码虽然短，但候选位置要拎清

排序法的思路也很有意思。排序之后目标元素出现 N 次，必然占据一个长度为 N 的连续区间。而你需要的只是判断这个区间到底覆盖了排序数组中间的两个位置中的哪一个。

def repeatedNTimes(nums): n = len(nums) // 2 nums.sort() if nums[n - 1] == nums[n]: return nums[n] if nums[n - 1] == nums[n - 2]: return nums[n - 1] return nums[n]

为什么答案一定在 nums[n-1] 和 nums[n] 这两个位置里？因为目标区间长度为 N，起点可以是 0 到 N 之间的任意位置。区间起点为 0 时，区间覆盖 [0, N-1]，包含 nums[n-1]；起点为 N 时，覆盖 [N, 2N-1]，包含 nums[n]；起点在中间任意位置时，两个中间位置至少有一个被区间包住。

但直接返回 nums[n] 是不行的，反例是 [1,1,2,3]（N=2），排序后中间两个位置是 nums[1]=1 和 nums[2]=2，答案在 nums[1] 而不是 nums[2]，所以必须做三步判断。我见过很多人栽在这里，以为“排序后返回中间位置”就够了，其实中间两个位置要分情况讨论。

3.3 间隔法： O(1) 空间的最优解

基于第 2 节的定理，间隔法的代码非常短，但边界处理必须小心。

先给一个最安全的版本，检查每个位置和它后面第 1、2、3 个位置是否相等，同时保证遍历覆盖所有可能的“较前位置”：

def repeatedNTimes(nums): n = len(nums) for i in range(n - 1): for d in (1, 2, 3): if i + d < n and nums[i] == nums[i + d]: return nums[i] return nums[-1]

i 的范围要到 n-2，而不是 n-3 或更短。原因很简单：任何一对下标差不超过 3 的相同元素，较前的那个下标最多是 n-2（因为后面还要给它匹配一个位置）。只有遍历到每个较前位置，才能保证所有满足条件的配对都不会漏掉。

还有另一个更经典的简化版本，只检查距离 1 和 2，找不到就返回最后一个元素：

def repeatedNTimes(nums): n = len(nums) for i in range(n - 2): if nums[i] == nums[i + 1] or nums[i] == nums[i + 2]: return nums[i] return nums[-1]

这个版本为什么也能保证正确？因为 N>2 时，用类似的反证法可以证明必有一对目标元素下标差不超过 2；而 N=2 时，只有一种情况会让距离 1 和 2 的检查全部落空：两个目标元素只能放在首尾两个位置。这种情况下最后一个元素正好就是目标，兜底返回它没有问题。两个版本可以在面试时都提一遍，讲出差异，反而显得理解深刻。

3.4 复杂度对比与怎么选

面试的顺序建议：先给哈希表拿分，再被追问时推出间隔法，把“为什么检查 3 个距离就够”的证明讲清楚。排序法可以作为第三种解法口头提一下，显示你思维够宽，但不要把它当主答案，毕竟它在时间复杂度上不是最优的。

4. 边界条件和代码实现中的三个坑：踩过的人才懂

4.1 遍历范围错了，真的会返回错误答案

我见过很多“差不多能跑通”的写法，其中最容易出问题的就是循环边界。比如有人写检查距离 1、2、3 的版本时，循环范围写成 range(len(nums) - 3)，理由是怕 i+3 越界。这个做法有真实的漏洞。

举一个实际会挂的反例：数组 [2,1,1,3]，N=2，目标是 1，它出现在下标 1 和 2，距离为 1。如果你用 range(len(nums)-3)=range(1)，就只会遍历 i=0，检查的是 0 和 1、0 和 2、0 和 3，全都不相等，循环结束兜底返回 nums[-1]=3，直接错掉。原因就是距离为 1 的那一对的较前下标是 1，而你的循环根本走不到 i=1。

所以最稳妥的做法是让循环遍历到 n-2，内层再单独做越界判断。宁可判断条件多一点，也不要让“配对”漏出扫描范围。

4.2 N=2 时的特殊排列，是兜底逻辑的来源

为什么简化版里“检查距离 1、2，找不到就返回最后一个元素”能安全兜底？把 N=2 的情况单独拎出来看就清楚了。

N=2 时数组长度是 4，目标元素出现 2 次，其他两个元素各出现 1 次。两个目标元素下标差只有三种可能：1、2、3。

• 差为 1：相邻，检查距离 1 命中。
• 差为 2：隔一个位置，检查距离 2 命中。
• 差为 3：只可能是下标 0 和 3，也就是一个在数组头、一个在数组尾。此时检查距离 1 和 2 都找不到它俩的配对，但数组最后一个位置恰好就是目标，兜底返回最后一位是正确的。

换句话说，兜底分支处理的是“N=2 且目标元素首尾相隔”这个唯一的特殊情况。能把这一条说清楚，就说明你不是背代码，而是真的推导过。

4.3 别拿摩尔投票硬套这道题

有些刷过“多数元素”的同学会下意识想：这题能不能用摩尔投票？不行。摩尔投票解决的是出现次数超过一半的问题，而这里目标元素只是恰好等于一半，不是超过一半。在目标元素出现次数恰好一半，并且其他元素互不相同的情况下，摩尔投票的正确性没有保障。

举个例子：数组 [1,2,1,3,4,1]，N=3，目标 1 出现 3 次，其余 2、3、4 各一次。按摩尔投票的抵消规则走一遍，候选者会因为非目标元素的依次抵消而在某个时刻变成 3 或 4，最后不一定留在 1 上。所以这道题不建议用摩尔投票思路，间隔法就是针对“恰好一半”这个特殊结构设计的最优解。

4.4 哈希计数为什么不需要“数到 N”

哈希表法最直觉的实现是“计数到 N 就返回”，但更省事的是“第一次碰撞就返回”。因为其他元素都唯一，第一次碰撞必然发生在目标元素第二次出现时，此时它的出现次数还远没到 N。如果非要用计数到 N，代码就多写一个字典，内存开销也更大。

不过这里有一个隐藏前提：只有当你确认“其他元素各出现一次”时，“第一次碰撞”策略才安全。如果把题目条件放宽，去掉这个唯一性约束，第一次碰撞的可能是别的元素，必须计数到 N 才能确定。这道题的条件刚好保证了哈希表法能做到最简。

5. 延伸思考：去掉“其他元素唯一”这个条件，题目还成立吗

5.1 间隔法会瞬间失效

间隔法之所以敢“见到一对相同的数就返回”，核心依赖是：只有目标元素会出现两次以上。一旦这个条件被打破，间隔法就不可用了。

构造一个反例：数组 [x,1,1,2,x,x]，N=3，x 出现 3 次，是合法的“出现 N 次元素”，1 出现 2 次，2 出现 1 次。你看一眼就知道答案是 x，但间隔法遍历到下标 1 时会发现 nums[1] 和 nums[2] 都是 1，然后立刻返回 1，直接给错答案。因为间隔法本质上是在找“第一处相邻或相近的重复”，而不是在找“出现 N 次的元素”。这个区别很微妙，很多人没意识到。

5.2 更一般情况的通用解法

如果题目真的放宽成“只保证存在一个出现 N 次的元素，其他随意”，那么最稳妥的做法就是哈希计数，等某个数的出现次数达到 N 就返回它：

def findRepeatedN(nums): n = len(nums) // 2 cnt = {} for x in nums: cnt[x] = cnt.get(x, 0) + 1 if cnt[x] == n: return x

此时“第一次碰撞”不再可靠，必须确认次数达标。空间复杂度回到 O(N)，也说明“其他元素唯一”这个条件其实才是 O(1) 空间解法的真正门票。

如果连“目标元素的出现次数 N 是全场唯一达标次数”都不保证，那就得重新定义题目了，可能会出现多个元素都重复 N 次的情况。那种情况下问题本身就有歧义，不是今天我们讨论的范围。

5.3 和“超过一半”题型的边界辨析

把这道题和经典“多数元素”放一起看非常有意思。多数元素的问题是“找一个出现次数超过 n/2 的元素”，摩尔投票能在 O(1) 空间解决，逻辑是让不同元素互相抵消，剩下的就是候选。而这道题的目标恰好只占一半，并且其他元素全是单份，反而不能用抵消的思路。

差别在于“超过一半”意味着多数元素不会被完全抵消光，而“恰好一半”则可能被对面 N 个唯一元素逐个抵消干净，最后候选者是谁就完全取决于排列顺序。所以下次做题时先判断是“超过一半”还是“恰好一半”，再决定用哪种套路。这个判断本身，往往比写代码更值钱。

这道题我反反复复练过很多次，也在给人讲题的时候用过。个人最大的体会是：能写出间隔法的人不算少，但能把“为什么兜底返回最后一个元素是安全的”讲清楚的人真的不多。很多人记住了“隔 1、隔 2 找不到就返回最后一位”这个结论，却不知道它其实是 N=2 时唯一漏掉的情况下在兜底。如果你下次再遇到这道题，建议先花三十秒把数组长度和目标出现次数的比例写出来，再想解法。比例关系才是这一类题真正的题眼。