刷算法题的时候最烦的就是那种“看着简单一写就错”的题目。今天要聊的这道“在长度 2N 的数组中找出重复 N 次的元素”就是典型的代表。它出现在不少公司的笔试题单里难度标记不高但解法里藏着一个非常巧妙的思维模型。如果你只会用哈希表硬怼那确实有点浪费这道题的价值。先花十秒钟看清题目条件数组长度为 2N其中有一个元素恰好重复了 N 次剩下 N 个元素互不相同让你找出这个重复 N 次的元素。注意题目没说数组有序也没说元素是整数范围内的连续值更没说你可以额外开多大的空间。从笔试角度说这题考的不是你会不会用unordered_map计数而是你能不能从“重复 N 次”和“长度 2N”这两个数字里读出潜台词。这篇文章我会从题目约束的拆解讲起依次给出暴力解、优化解、最优解三种方案重点讲清楚为什么“窗口大小为 3”就能覆盖所有情况然后补充正确性证明、常见卡壳点排查以及这个思维模型在其他题目里的迁移方式。无论你是刚刷题的新手还是准备面试的老手这题都值得花二十分钟彻底吃透。1. 题目约束里的数学气息2N、N 次、互不相同的含义先说结论这道题真正难的地方不是找重复元素而是你能不能意识到“重复 N 次”和“其余 N 个元素互不相同”这两个条件叠加在一起之后会产生一个非常强的结构限制。我最早刷这题的时候第一反应就是排序或者计数压根没往数学上想结果被一个“窗口长度固定为 3”的解法秒杀心态直接崩了。1.1 三个关键条件的叠加效应拆开看这三个条件数组长度是 2N说明数组里一共有 2N 个位置。有一个元素重复了 N 次说明这个元素占掉了数组一半的位置。其余 N 个元素互不相同说明剩下的位置被 N 个不同的值填满任何一个非重复元素最多出现一次。把这三句话拼在一起你能推出什么重复元素出现的频率是 1/2而且是唯二可能超过一次的“高频元素”。数组中除了它其他所有元素都是“孤家寡人”。这意味着什么意味着你在数组中任意取两个位置如果这两个位置上的值相同那么它们必然都是那个重复 N 次的元素——因为其他元素根本没有机会出现两次。这个推论看起来平淡无奇但它是后面所有优化解法的地基。哈希表解法本质上就是在利用这个性质只要某个值第二次出现直接返回它不需要等统计完整个数组。随机抽样解法也是基于“元素占一半抽到它的概率是 50%”这个事实。而最优解里的鸽巢原理更是把这个性质逼到了极致。1.2 为什么这题不能用“找出现次数最多的元素”的套路硬解如果你拿这道题去套“多数元素”的经典解法摩尔投票你会发现它并不是最合适的。摩尔投票解决的是“出现次数大于 n/2 的元素”前提是众数存在且严格过半。这里重复元素刚好占 1/2恰好等于一半不是大于一半。虽然从频率上看它已经是最高的但“最高频”和“严格过半”是两个不同的概念摩尔投票的正确性证明依赖“计数会相互抵消”在等于一半的情况下边界处理会变得非常恶心。同样的道理也不能把问题转化成“找到唯一出现多次的元素”后用异或处理。异或适合处理“只有一个元素出现奇数次其他都出现偶数次”的场景这题里其他元素是出现 0 次或 1 次不是偶数次直接异或会把结果搞乱。所以这题的约束条件决定了它的最优解法不在“比拼频率”这个思路上而是在“利用物理位置关系”上。这就是为什么后面要引入窗口和鸽巢原理。2. 解法演进从暴力哈希到 O(1) 空间的鸽巢原理我刷题有个习惯拿到一道题先写最暴力的解法确保思路正确然后再一步步优化。这样做的好处是你能明确感知到每一步优化到底在解决什么问题。下面按我的思考路径依次给出三种解法。2.1 解法一哈希表计数5 分钟就能写出来的保底方案最不用动脑的方法就是遍历数组用一个哈希表记录每个元素出现的次数遇到某个元素次数达到 N 就直接返回。int repeatedNTimes(vectorint nums) { unordered_mapint, int cnt; for (int x : nums) { cnt[x]; if (cnt[x] nums.size() / 2) return x; } return -1; // 题目保证有解不会到这 }这段代码的时间复杂度是 O(N)空间复杂度是 O(N)因为哈希表在最坏情况下要存下 N 个不同的值加上那个重复元素。笔试中这个答案可以拿满分毕竟题目没限制空间而且大多数面试官会先接受这个方案再问你“能不能优化空间”。但注意一个细节我提前判断了cnt[x] nums.size() / 2而不是等整个数组遍历完再找最大值。这是利用题目条件“重复元素恰好出现 N 次”做剪枝。因为长度为 2N一旦某个元素计数达到 N它就是我们要找的元素不需要继续遍历。这个小优化虽然不改变复杂度量级但能减少平均遍历次数也体现了你确实读懂了题目约束。2.2 解法二随机抽样用概率换空间如果你看过某些公司的面经可能会发现还有随机抽样的解法。思路很简单元素占了数组一半的位置那你随机抽一个下标抽到重复元素的概率是 50%随机抽两个不同的下标至少有一个是重复元素的概率是 75%。按这个思路随机抽两个位置如果值相同就直接返回如果不同就再抽。数学期望上抽几次就能命中。int repeatedNTimes(vectorint nums) { int n nums.size(); while (true) { int i rand() % n; int j rand() % n; if (i ! j nums[i] nums[j]) return nums[i]; } }这个解法空间复杂度是 O(1)代码也非常短但有个问题最坏情况下可能永远抽不到两个相同元素虽然概率极低。面试里你敢写这个方案其实是想展示自己对概率和随机化的理解但有些面试官会追问“你能保证一定在有限次内结束吗”这就比较尴尬。所以它更适合作为思路拓展不适合作为最终交付方案。我个人建议在面试时提一嘴“随机抽样的思路能到 O(1) 空间但不够确定”然后引出下面真正的 O(N) 时间 O(1) 空间解法观感最好。2.3 解法三鸽巢原理 固定窗口正解长这样现在进入核心。重复元素在长度为 2N 的数组里出现了 N 次剩下 N 个位置被互不相同的元素占满。现在想象你把所有重复元素的位置标记出来一共有 N 个标记分布在这个长度为 2N 的数组里。因为非重复元素不会重复那么任意两个相邻位置如果值相同必然是重复元素。但问题来了重复元素的 N 个位置并不一定相邻它们可能被其他元素隔开比如一个隔一个像[A, X, A, Y, A, Z, ...]。这种情况下你检查相邻位置是找不到两个相同元素的。这时候就需要鸽巢原理出场了。把数组分成 N 个长度为 2 的小组位置(0,1),(2,3),(4,5)...。因为重复元素有 N 个但只有 N 个小组如果每个小组最多放一个重复元素那么 N 个小组刚好每个小组都放了一个。这本身不矛盾。但如果某个小组放了两个重复元素那么这两个元素相邻你直接检查相邻位置就能发现。麻烦的恰恰是“每个小组恰好一个”的情况比如[A, X, A, Y, A, Z]这种交替排列。关键来了如果每个长度为 2 的小组里都恰好有一个重复元素把小组内部的顺序打乱会发生什么比如第一个小组(A, X)第二个小组(A, Y)第三个小组(Z, A)。你会发现只要重复元素在相邻小组里出现的位置差异不超过一个下标那么隔一个位置的地方下标差 2就会出现两个相同的重复元素。换句话说要么相邻两个位置下标差 1相同要么隔一个位置下标差 2相同要么首尾两个位置相同——这三种情况至少发生一种。这个结论就是窗口大小为 3 的由来。严谨点说把数组看作环形结构重复元素出现 N 次分布在 2N 个槽位里。如果任意两个重复元素之间的距离都大于等于 3即下标差至少为 3那么 N 个重复元素至少需要1 2*(N-1) 2N - 1个槽位才能放下第一个元素占 1 个槽位之后每个元素与前一个相隔至少 2 个空槽位所以每个额外元素需要 2 个新槽位。但这和数组只有 2N 个槽位矛盾因为2N - 1 2N不成立恰好等于2N - 1是允许的等一下仔细算2N - 1确实小于等于2N所以这个推导还不够强。正确的推法是如果任意两个重复元素的距离都大于 2即下标差至少为 3则 N 个重复元素占据的位置跨度至少为1 3*(N-1) 3N - 2当 N 2 时3N - 2 2N恒成立因为3N - 2 - 2N N - 2要 N 2 才行。当 N 1 时数组长度是 2只有一个元素出现一次其他一个元素一次这不符合“重复 N 次”的设定因为 N1 时重复 1 次就是出现 1 次构不成“重复”题目实际要求 N 2。所以当 N 2 时必然存在两个重复元素的下标差不超过 2。下标差不超过 2意味着什么意味着在数组中存在两个相等的元素它们在原数组中的距离是 1 或者 2。所以只要检查所有下标差为 1 和 2 的位置对如果发现相等就返回。但还有一个边界情况如果数组是循环的距离 2 还要考虑首尾相接的情况不过更稳妥的做法是直接把首尾两个元素单独比较一次覆盖环形距离为 1 的情形。于是标准解法就是两层循环第一层比较相邻元素(i, i1)第二层比较间隔一个的元素(i, i2)最后比较(0, n-1)。int repeatedNTimes(vectorint nums) { int n nums.size(); for (int i 0; i n - 1; i) { if (nums[i] nums[i 1]) return nums[i]; } for (int i 0; i n - 2; i) { if (nums[i] nums[i 2]) return nums[i]; } return nums[0]; // 此时必然是首尾相同 }注意第二个循环结束后如果还没返回说明相邻和隔一位都没找到相同元素。根据上面的推论唯一剩下的可能就是首尾两个位置相同所以直接返回nums[0]即可。这个解法的代码量比哈希表还短时间 O(N)空间 O(1)而且没有任何随机性是完全确定的算法。3. 为什么窗口大小是 3 而不是 4 或 5完整推演与正确性证明很多人看完上面的代码会有一个疑问你检查了距离 1 和距离 2凭什么不漏距离 3 就不需要检查吗这个问题问得非常好因为答案并不是“直觉上够用”而是有严格数学推导的。这节我展开讲清楚顺便帮你在面试时能顶住追问。3.1 反证法推演距离上限假设数组中任意两个重复元素的下标差都大于 2即最小距离至少为 3。把重复元素按从左到右的顺序记为p1, p2, ..., pN。为了不让任何两个重复元素距离不超过 2我们必须让p2与p1至少相隔 3p3与p2至少相隔 3以此类推。那么pN - p1 3 * (N - 1)。因为数组长度为 2N索引范围是 0 到 2N-1最大跨度pN - p1 2N - 1。所以3*(N-1) 2N-1化简得3N - 3 2N - 1即N 2。也就是说当 N 3 时必然存在一对重复元素的距离不超过 2。这里有一个临界情况 N 2此时数组长度为 4重复元素出现 2 次其余 2 个元素互不相同。如果两个重复元素分别在下标 0 和 3那么距离是 3确实不存在距离 1 或 2 的重复对。但别忽略首尾比较下标 0 和 3 在环形意义下距离是 1所以首尾比较会命中。这就是为什么代码末尾要单独比较一次nums[0]和nums[n-1]。把 N 2 的情况代入你会看到窗口检查逻辑依然成立。N 1 的情况题目不会给因为“重复 1 次”没意义长度 2 的数组只有两个互异的元素找不到“重复 N 次”的目标。所以实际上窗口大小 3 已经覆盖了所有合法输入。3.2 把证明翻译成更容易理解的盒子模型如果你觉得上面的不等式推导太抽象我换个说法。想象数组是 2N 个连续的盒子排成一行你要把 N 个红球放进盒子每个盒子最多放一个红球剩下的盒子放白球互不相同的非重复元素。题目说白球彼此都不同所以白球不是重点重点只是红球的位置分布。现在问有没有可能任意两个红球之间至少隔着两个白球也就是红球间距至少为 3。假设可能那 N 个红球需要占据的盒子跨度至少是“第一个红球 每加一个红球多占 3 个盒子”总共至少1 3*(N-1) 3N - 2个盒子。当 N 2 时需要 4 个盒子数组恰好有 4 个可能实现比如红 白 白 红。当 N 3 时需要 7 个盒子但数组只有 6 个不可能实现。当 N 更大时更不可能。所以 N 3 时必然有两个红球距离不超过 2。而 N 2 的唯一“间距为 3”排布是首尾各一个红球首尾比较能覆盖。窗口大小 3 就在这个意义上够用了。3.3 能不能把检查窗口缩到更小为什么不行你可能还想问既然距离上限是 2那我只检查相邻两个距离 1行不行答案是不行因为存在交替排列的情况比如[A, X, A, Y]重复元素 A 出现在下标 0 和 2相邻位置(0,1)是 A 和 X 不相同(1,2)是 X 和 A 不相同(2,3)是 A 和 Y 不相同。如果只检查相邻位置就漏掉了 A。这就是窗口必须覆盖距离 2 的原因。那距离 3 要不要检查按照 3.1 的证明N 3 时不需要N 2 时唯一可能漏掉的距离 3 情况会被首尾比较兜底。所以这个解法的完整检查集合是所有相邻对、所有距离为 2 的对、以及首尾对。把这三类合并起来正好覆盖了“距离不超过 2 或环形距离为 1”的所有可能命中场景。3.4 正确性证明的最后一块拼图找到即正确还有一个细节需要确认如果检查过程中发现nums[i] nums[i1]这个值一定就是重复 N 次的元素吗是的因为除了重复元素其他所有元素都互不相同任何一个非重复元素不可能在数组中出现两次。所以一旦找到两个下标不同但值相同的位置这个值必然是那个占了一半位置的重复元素。这也是题目条件里“其余 N 个元素互不相同”的真正价值——它让“找到一对相同”和“找到目标元素”完全等价。如果把“其余 N 个元素互不相同”这个条件去掉上面的窗口解法立刻失效。比如数组[A, X, A, X]中 A 出现 2 次但 X 也出现 2 次符合“长度 4某个元素重复 2 次”的字面描述可一旦你找到(0,1)位置的 X 和 X你就会误以为 X 是答案。所以做这道题时务必先向面试官确认“其余元素是否保证互异”如果题目没有这个条件最优解就变了得回到哈希表或者排序。这一点我会在后面的排查清单里再强调。4. 实操中的边界情况和常见卡壳点排雷算法题最有价值的部分往往不是“会写解法”而是“知道哪里会写错”。这道题代码短但坑点一点不少。我把这些年刷题、讲解时遇到的典型问题整理成一份排查清单你对照着检查能省不少调试时间。4.1 数组越界第二个循环的上界到底怎么取新手最容易犯的错是第二个循环写成i n然后访问nums[i 2]时越界。正确的是i n - 2。但很多人搞不懂为什么不是n - 1。原因是你要访问i 2这个下标必须保证i 2 n - 1也就是i n - 3。因为循环条件是i n - 2即i最大取到n - 3刚好满足。同理第一个循环访问i 1条件是i n - 1。如果你用 Python 写range(n - 2)效果是一样的用 C 写for循环时尤其要小心别把和搞混。4.2 首尾比较的顺序问题代码里第三段如果写成return nums[n - 1]或者return nums[0]都可以因为首尾相等时两个值相同。但要注意这个第三段不能省否则 N 2 且重复元素分布在下标 0 和 3 时会漏检。举个例子nums [2, 1, 3, 2]长度 42 出现两次1 和 3 各出现一次。相邻对(0,1)值不同(2,3)值不同距离 2 的对(0,2)值不同(1,3)值不同。所有循环检查都找不到答案只有比较nums[0] nums[3]2 2才能命中。所以面试时背代码容易但理解为什么要有这一步才是真正加分的地方。4.3 用哈希表解法时别踩的“次数判断”陷阱哈希表解法里如果你写成“先统计完所有元素再找次数等于 N 的元素”逻辑上没错但代码会多一个循环。我个人更喜欢边统计边判断因为题目保证解存在且唯一一旦某个值计数达到 N 就可以提前返回。这里有一个容易让人困惑的点N nums.size() / 2如果用size_t类型size() / 2是整除没问题但如果你用int存数组长度也记得用int n nums.size()而不是直接拿size_t去和哈希表里的int比较避免无符号整数比较引发警告。虽然刷题环境一般不报错但好的编码习惯还是该有的。4.4 随机解法的死循环风险和 rand() 的局限如果你在面试里展示随机解法一定要主动说明“这个解法不确定只是预期复杂度 O(1)”。实际写的时候还需要避免i j的情况不然同一个位置和自己比较如果元素恰好就是重复元素那其实也能返回正确结果但语义上不够严谨比如i j时nums[i] nums[j]恒成立会直接返回当前元素这在任何情况下都是错的吗其实不是。因为任意一个位置上的值无论是重复元素还是非重复元素都满足“和自己相等”所以如果不加i ! j限制第一次随机抽样就会直接返回nums[i]而nums[i]可能不是重复元素。这是随机解法里最隐蔽的坑。要保证返回的一定是重复元素必须要求i ! j且两个位置值相同。4.5 输入规模极小的情况数组长度 2NN 最小是多少按题目语义“重复 N 次”N 至少为 2。所以数组最小长度是 4。但如果你自己造测试数据想验证 N 2 的情形务必包含[A, B, C, A]这种首尾重复的用例以及[A, B, A, C]这种距离为 2 的用例这样才能覆盖窗口解法的所有分支。我真见过有人只测了[A, A, B, C]这种相邻重复的用例然后沾沾自喜说解法正确结果一提交就挂。所以自测时要有意识地制造“最分散”的分布让重复元素尽可能均匀地铺开间距拉大才能触发首尾分支和距离 2 分支。5. 从这道题抽象出来的思维模型鸽巢距离窗口这道题做完就完了吗不是的。它的价值在于抽象出“鸽巢距离窗口”这个思维模型。很多看似无关的题目底层逻辑都可以迁移过去。我给你列几个典型的例子你自己品一品。5.1 在“存在重复元素”类题目中的应用LeetCode 上有一类基础题叫“存在重复元素”问你一个数组里有没有任意两个元素相等。最直接的解法是排序后扫一遍或哈希表去重但如果你把数组视作长度为 n 的序列那么“找重复”本质上是在问“有没有哪两个元素的距离为某种模式”。当元素范围有限时比如元素值都在[1, n]之间且部分缺失你可以用鸽巢原理直接判断n1 个元素放进 n 个桶必有重复。这类题的核心就是“元素数大于桶数必定碰撞”和 2N 数组里 N 个重复元素的推导是同一套逻辑。当你把重复元素看作“必须装进盒子里的红球”时碰撞位置的上界就是窗口大小的理论来源。5.2 与“长度为 n 的数组包含 1 到 n-1 的整数”这类题的联系另一个经典套路是一个长度为 n 的数组元素值范围是 1 到 n-1让你找重复值。这题最常见的是“原地标记”或者“快慢指针”解法。它的本质和本题一样值域大小比数组长度小至少有一个值要占用两个位置所以重复大概率发生在某个局部范围内。快慢指针找环的做法其实是把“下标跳转”模拟成链表“重复值”对应“环入口”也是鸽巢思想的一种体现。你先把 2N 数组这道题吃透再去做“找环入口”那道题思维衔接会非常顺畅因为它们都在回答同一个问题当资源数大于槽位数时冲突发生在哪里。5.3 二维场景下的迁移思考如果把一维数组扩展到二维比如在一个M x N的网格里有某种元素超过了一半的格子问你能否在 O(1) 空间内找到它。答案是可以的。因为它超过了一半任意一个2 x 2的小窗口里必然至少出现一次而相邻窗口会有重叠你可以通过特定的扫描顺序锁定它。这个思想在图像处理里的“众数滤波”等场景也有应用。虽然刷题不会直接考二维版本但理解了一维的推导过程你就能自己设计出二维的模拟退火式搜索算法这对思维训练非常有益。5.4 实际工程里的应用场景说个题外话这种“固定窗口 鸽巢距离”的思想在工程上也有用。比如你在处理一个日志序列想快速找出某个重复出现的高频事件如果已知某个事件占了一半以上的时间戳你可以只检查相邻时间戳和间隔一个时间戳的位置而不需要维护全局计数器。这种方法的优势在于内存占用与事件种类无关只与窗口大小相关特别适合数据流场景。虽然生产代码里大家习惯用 Bloom Filter 或 HyperLogLog但在某些嵌入式环境或者极度节省内存的场景下这种确定性算法反而更香。6. 面试答题节奏和代码演示建议最后聊点面试向的东西。这道题在面试中经常作为“从暴力到最优”的考察题面试官想看的不是你直接背出最优解而是你如何一步步分析、优化、证明。我根据多次模拟面试的经验给你一套比较稳妥的答题节奏。6.1 先复述题意并确认约束拿到题目先别急着写代码。礼貌地确认“数组长度是 2N有一个元素出现 N 次其余元素都互不相同对吗”这一句确认很关键因为如果面试官临时把条件改成“其余元素可能重复”后面的所有优化思路全要推翻。你主动确认条件说明你读题严谨也给自己争取了思考时间。6.2 先给暴力解再说优化方向第一轮先讲哈希表计数并说明复杂度 O(N) 时间、O(N) 空间。面试官通常会追问“可以优化空间吗”这时候你可以提随机化思路顺带指出它的缺点然后引出鸽巢原理。如果你一上来就写窗口解法面试官反而可能怀疑你是不是背题。先给暴力解再给最优解展示的是你的思考路径比直接甩最优解可信得多。6.3 写代码时讲出关键证明写窗口解法的过程中我会边写边讲“这里我检查距离为 1 和 2 的位置对因为如果所有重复元素间距都大于等于 3N 个重复元素至少需要 3N-2 个位置当 N3 时超出数组长度 2N矛盾。N2 的特殊情况由首尾比较兜底。”这段话不一定要完整背下来但至少要让面试官感觉到你对“为什么窗口大小是 3”有严格论证而不是碰运气。6.4 主动补充边界测试用例写完代码后主动给出测试用例比如[1, 2, 3, 1]验证首尾分支[1, 2, 1, 3]验证距离 2 分支[1, 1, 2, 3]验证相邻分支。你可以说“这三个用例覆盖了三种命中情况分别对应相邻、隔一位、首尾。”然后口头模拟一遍执行过程确认返回结果。这个习惯在面试里非常加分因为很多候选人写完代码就直接说“没问题”实际上自己都没跑过。6.5 复杂度讨论和延伸提问的应答思路面试官可能会问“如果数组特别大比如 10 亿个元素但只有一个重复元素占一半你的算法还能跑吗”答案是可以的因为时间 O(N)空间 O(1)而且一次顺序遍历就能完成不需要额外存储。你甚至可以提一句“这个算法是数据流友好的”因为它在遍历过程中只需要记住当前位置和前后几个位置的值不需要回溯很远的距离。这在面试官眼里是加分项说明你有工程直觉。还有可能的追问是“如果重复元素不是 N 次而是大于 N/2但其他元素也可能重复这题还能用窗口解吗”答案是不能。因为“其他元素也可能重复”破坏了“找到两个相同值就一定是目标元素”的等价性。此时应该回到摩尔投票或哈希表。你可以预判这个追问主动说明这个解法的适用边界会显得你理解得很透彻。7. 刷题之后的个人体会别急着刷量先把一道题榨干写到这里我想说点题外话。很多人刷题喜欢一天刷十几道每道题看一眼题解、抄一遍代码就算过了。但这道 2N 数组题目如果只是背下窗口解法的代码那你收获的东西非常有限。真正值得花时间的是那个“为什么窗口大小是 3”的推导过程以及“距离不超过 2 必然存在”这个结论的证明思路。把这个思路吃透比多做十道简单题更有用。我在实际刷题过程中发现把一道题从暴力解到最优解、从实现到证明、从单一题目到同类题目迁移整个过程大概需要四十分钟到一小时但带来的思维提升远超囫囵吞枣地刷十道题。尤其是这种“从数学约束直接推出算法结构”的题目正是面试官最喜欢考察的核心能力也是很多人在笔试中栽跟头的原因。如果你正在准备面试建议把这道题作为“如何分析题目约束”的经典案例反复琢磨直到你能不看题解独立推导出窗口大小为 3 的解法那就算真正掌握了。顺带分享一个小技巧我在本地做题时会给窗口解法加一段验证代码随机生成大量满足条件的测试数组然后用哈希表解法做基准对比两种解法结果是否一致。这样跑几百组随机数据我就能对解法的正确性非常放心。等你日后遇到类似的“数学推导型”题目也可以用这套“随机生成 暴力验证”的方法来检验自己的解法是否正确——它能帮你发现很多手推证明时容易忽略的边界情况。