这题我愿称之为“最容易被过度设计的简单题”。第一次在题库里翻到“在长度 2N 的数组中找出重复 N 次的元素”时，我脑子里冒出来的第一反应是：又要上哈希表数次数了。但等我耐着性子把题干里的三个条件逐条读完之后，才意识到这题考的根本不是数据结构的熟练度，而是你有没有把“约束条件”当成解题线索的习惯。如果你正在准备算法面试，或者正在刷数组类的题目，这题是个极好的“读题比写代码更重要”的案例。它的难度放在 LeetCode 里只能算简单偏下，但里面藏着的数学推导非常典型，适合刚接触刷题的新手用来建立“条件敏感度”，也适合有经验的人拿来反推自己是不是一上来就无脑哈希。整道题的代码量不超过十行，但是把“为什么能这么写”讲清楚，比AC二十道题都有用。1. 题目拆解：读懂“重复 N 次”背后的隐藏条件1.1 题干到底在说什么题目本身的表述非常克制，一共给了三条信息：数组长度是2 * n，偶数。数组里有n + 1个互不相同的元素。其中恰好有一个元素重复了n次，其余元素都只出现一次。最后要求你把这个重复了n次的元素找出来。很多人会忽略第二条里“互不相同”这四个字，但整道题能不能做到O(1)空间，靠的就是它。稍微翻译一下：既然总共有n + 1种不同的值，而数组长度是2n，那意味着这n + 1种值里，只有一种值的出现次数大于 1，其他每一种最多出现一次。又因为题目明说了“恰有一个元素重复n次”，所以剩下的n种值在数组里就是各出现一次，不多不少。这个结论看起来平淡，但它直接导出一个使用率极高的性质：只要在数组里看到某个值出现了第二次，这个值就一定是答案，不需要继续数下去。这个性质是所有“提前返回”解法的基础。1.2 这个条件能榨出什么信息我刷题时有个习惯：每读到一个条件，都会在草稿纸上写一下“这个条件能推出什么”。这题的三个条件放在一起，能推出的信息其实比表面看上去多得多。数组长度是2n，答案出现n次，说明答案的出现频率恰好是二分之一。但注意，它和“摩尔投票法”那类“出现次数超过一半”的题目有本质区别。超过一半意味着答案的数量比所有其他元素加起来还多，而这题里答案的数量只是和其他元素的数量打了个平手。所以如果你第一时间想到摩尔投票，这题大概率会翻车，后面我会专门说为什么。另一个能推出来的信息是：因为其他n个元素各不相同，它们之间永远不会产生“相邻相等”的情况，唯一会制造相邻重复的就只有答案本身。换句话说，一旦数组里出现了任何一对相邻或近邻相等的元素，这对元素一定和答案有关。这个观察是O(1)空间解法的核心线索。2. 解法一：哈希表计数，最稳妥也最容易想到的答案2.1 思路与代码实现先说最直接的暴力方案：遍历数组，用一个集合记录已经见过的值，遇到已经在集合里的值就直接返回。因为其他元素都是唯一的，所以第一个被重复访问到的值必然是答案。def repeatedNTimes(nums): seen = set() for num in nums: if num in seen: return num seen.add(num)这段代码可以说是“闭着眼都能写”的那种。我第一次做这题的时候也是这么写的，跑了一遍测试就过了。如果用 C++ 写，思路完全一样：class Solution { public: int repeatedNTimes(vector<int>& nums) { unordered_set<int> seen; for (int num : nums) { if (seen.count(num)) return num; seen.insert(num); } return -1; } };这里要注意一个细节：为什么“第一个重复出现的值”一定是答案，而不是其他元素？因为题目说了，除了答案以外的n个元素全部互不相同，它们在数组里只会出现一次，永远不会被第二次遇到。答案出现n次，且n至少为 2（否则题目就没意义了），所以遍历过程中答案一定会被第二次遇到，而其他元素不可能，因此第一次触发seen里已存在的值，必然是答案。2.2 复杂度分析与适用场景哈希解法的时间复杂度是O(n)，空间复杂度是O(n)，因为最坏情况下要把前n个不同元素都存进集合里才能遇到答案的第二次出现。这个解法在面试里完全可以作为“我想到了什么”的第一步回答。它正确、简洁、不容易出 bug。但说实话，如果面试官接下来问你“能不能把空间复杂度降到O(1)”，你就需要立刻意识到，题目里“其他元素互不相同”这个条件还没有被充分使用。这时候顺着条件往下挖，才有机会展示真正的解题能力。我自己在实际刷题复盘的时候，会刻意把哈希解法标记为“保底答案”，它的价值是让你先有正确解，再优化。如果你一上来就死磕最优解，卡住了连保底分都拿不到。面试也一样，先给能干活的方案，再讲更优雅的方案，观感会好很多。3. 解法二：排序后找相邻相等，思路简单但要注意陷阱3.1 思路与代码实现另一种不需要哈希表的办法是排序。排序之后，相同的值会聚在一起。因为答案是唯一出现多次的元素，排序后的数组里，有一整段长度为n的区域全是同一个值。在这个连续段内部，必然存在至少一对相邻相等的元素。扫描一遍排序后的数组，找到第一对相邻相等，返回即可。def repeatedNTimes(nums): nums.sort() for i in range(len(nums) - 1): if nums[i] == nums[i + 1]: return nums[i]这个写法看起来很干净，但这里藏着一个很多人会踩的坑。我见过不少题解在排序之后直接返回nums[n]，理由是“答案占了一半，排序后中间位置的元素肯定是答案”。这个结论在部分用例下是对的，但并不是恒成立的。举个例子，数组[1, 1, 2, 3]，n = 2，排序后还是[1, 1, 2, 3]，nums[n]也就是nums[2]是2，但答案是1。再比如[5, 1, 5, 2, 5, 3, 5, 4]，n = 4，排序后是[1, 2, 3, 4, 5, 5, 5, 5]，nums[4]是5，答案恰好对上了。也就是说，排序后取中位数能不能赢，完全取决于答案的连续段起始位置在哪里，不能靠赌。3.2 排序解法为什么不推荐在面试里当主力排序的时间复杂度是O(n log n)，空间复杂度取决于排序实现，Python 内置sort是额外O(n)，C++ 的std::sort在某些实现下也需要递归栈空间。从效率上讲，它比哈希解法和相邻比较法都差一截。更关键的是，排序没有利用“其他元素互不相同”这个核心条件。你会发现，就算去掉这个条件，排序后找相邻相等的做法在“答案恰好是唯一重复元素”的前提下依然能跑通。换句话说，排序解法把一道三个条件的题目，降维成了一个纯堆数据结构的题目，这本身就是对题面信息的浪费。所以我的建议是：排序解法适合用来做验证，比如在你的代码跑出来之后，写一段辅助逻辑核对答案是否正确。面试回答时，如果你先讲了哈希，又讲排序，面试官会觉得你有一定积累，但没有挖掘题目的独特点。真正的亮眼操作，是搬出下面这个相邻比较法。4. 解法三：相邻比较法，把空间压到 O(1)4.1 抽屉原理的直觉理解先建立直觉。假设答案元素是x，它在数组里出现了n次。如果x的任何两次出现之间都不相邻，那它至少得隔开多远？如果任意两次出现之间至少隔两个位置，也就是索引差至少为 3，那么n个x要占据的最小跨度是第 1 个到第n个之间的总长度。放最紧凑也得是0, 3, 6, 9, ...这样摆，最后一个x会在索引3 * (n - 1)的位置。数组总长度只有2n - 1个索引可用，想要3 * (n - 1) <= 2n - 1成立，算一下就知道n最多等于 2。换句话说，只要n >= 3，答案的n次出现里，就必然能找到一对索引差为 1 或 2 的。而索引差为 1 就是相邻，索引差为 2 就是隔一个元素。这就是为什么我们只需要检查这两种距离，就能覆盖绝大多数情况。那n = 2的时候呢？数组长度 4，答案出现 2 次。最极端的摆放是放在索引 0 和索引 3，距离 3，确实躲过了距离 1 和距离 2 的检查。但别忘了前面说的性质：其他元素都是唯一的，所以除了答案之外，索引 0 到 3 里剩下的两个位置填的是两个互不相同的元素。此时索引 0 的位置一定是答案，兜底返回nums[0]就能拿到正确结果。4.2 为什么检查间隔 1 和间隔 2 就足够为了把这个结论讲得更严谨，我用分组法再过一遍。把2n个索引按相邻两两分组：(0, 1), (2, 3), ..., (2n-2, 2n-1)，一共n组。现在考虑答案x在这n组里的分布情况。第一种情况，x在某一组内部出现了两次。同一组的两个索引是相邻的，检查间隔 1 时就会命中，直接返回。第二种情况，x在每一组里最多出现一次。因为总共只有n组，而x恰好出现n次，所以它必须在每一组里都出现一次。这时候看前两组：第一组(0, 1)和第二组(2, 3)。x在第一组里要么在0，要么在1；在第二组里要么在2，要么在3。把所有组合过一遍：x同时出现在 0 和 2，索引差 2，间隔 2 检查命中。x同时出现在 1 和 2，索引差 1，间隔 1 检查命中。x同时出现在 1 和 3，索引差 2，间隔 2 检查命中。x同时出现在 0 和 3，索引差 3，前两种检查都漏掉。但注意，这四种里只有最后一种会成为漏网之鱼，而这恰好意味着nums[0]就是答案。所以算法最后兜底返回nums[0]，靠的就是这个结论。4.3 代码实现与边界处理def repeatedNTimes(nums): total = len(nums) # 检查间隔为 1 的相邻元素 for i in range(total - 1): if nums[i] == nums[i + 1]: return nums[i] # 检查间隔为 2 的元素 for i in range(total - 2): if nums[i] == nums[i + 2]: return nums[i] # 兜底返回第一个元素 return nums[0]C++ 版本：class Solution { public: int repeatedNTimes(vector<int>& 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]; } };代码里有两个边界需要留意。第一个循环到n - 2为止，保证i + 1不越界。第二个循环到n - 3为止，保证i + 2不越界。我第一次手写的时候，第二段循环条件写成了n - 2，结果最后一个位置访问越界，排查了半天。这种“多走一位”的边界错误，在数组类算法题里太常见了，写的时候心里要清楚最后一对合法组合是哪两个索引。这个解法的时间复杂度是O(n)，因为两轮循环各扫一遍，常数系数也就是 2。空间复杂度是O(1)，只用了几个变量。在面试里，这个答案就是本题的最优解。5. 三种解法对比与面试打法5.1 复杂度与优缺点横向对比解法时间复杂度空间复杂度代码量是否利用题目核心条件风险点哈希集合O(n)O(n)极少部分利用容易被追问能否省空间排序 + 相邻查找O(n log n)O(n)（取决于实现）少基本没利用排序后取中位数可能踩坑相邻比较O(n)O(1)极少充分挖掘边界写错导致越界从表里能一眼看出，相邻比较法在时间、空间、代码量三个维度都是最优的。但我不建议你直接跳过前两种解法直接写最优解，因为面试考察的不仅是“能不能 AC”，还有“你的思考过程有没有逻辑层级”。5.2 面试时按什么顺序讲我自己复盘面试场景时，总结出的比较稳妥的打法是三步走。第一步先说暴力思路：“看到重复元素，天然会想到用哈希集合记录已经见过的值，碰到第二个见过的值直接返回，这个做法 O(n) 时间和 O(n) 空间。”这么说，代码还没写，面试官就知道你有基本的数据结构能力。第二步抛出问题：“这个解法能不能优化？我注意到题目里有一条特殊条件——除了答案以外的元素都互不相同。这意味着数组里一旦出现相邻的重复值，几乎可以断定是答案。于是我们可以检查间隔为 1 和间隔为 2 的元素，如果都没找到，再返回第一个元素。这个推导是严格成立的，空间能压到 O(1)。”第三步如果面试官追问“为什么间隔 1 和 2 就够了”，你就有机会把第四节的抽屉原理和分组法讲一遍。讲到这，整个回答的深度就出来了。这里有一个很现实的经验：很多候选人会在第一步和第二步之间卡住，因为他们不知道从哈希到 O(1) 的桥梁是什么。桥梁就是题干里那个“其他元素互不相同”的条件。刷题的时候多养成“翻译条件”的习惯，面试时自然就有话讲。6. 常见问题与排查技巧实录6.1 边界条件与特殊用例这题我在测试时发现，最容易出问题的其实是小数组，尤其是n = 2的情况。数组长度只有 4，比如[1, 2, 3, 3]，间隔 1 直接命中nums[2] == nums[3]，没问题。但如果测试用例是[1, 2, 3, 1]，答案1出现在索引 0 和索引 3，间隔为 3。这时候间隔 1 和间隔 2 都查不出来，算法会走到return nums[0]，也就是返回1，正确。另一个边界是极端分布[1, 2, 1, 2]这类。等等，这个用例里出现了两个重复元素，不符合题目“n+1 个不同元素”的前提，所以它根本不会出现在合法测试集里。我拿它测试只是因为想确认算法在非法输入下不会写出越界异常，这个从工程健壮性角度算一个加分项，但不是必须的。写单元测试的时候，我通常会覆盖几类典型场景：答案在数组开头连续出现：[3, 3, 1, 2]答案在数组末尾连续出现：[1, 2, 3, 3]答案均匀分布且首尾相隔最大：[1, 2, 3, 1]答案在中间隔一个位置：[2, 1, 2, 3]把这几个用例跑通，代码基本就稳了。6.2 这题最容易踩的三个认知误区第一个误区是直接套摩尔投票法。我见过不止一个人在讨论区里贴摩尔投票的代码，但它在这题里是错的。摩尔投票的前提是候选元素出现次数超过一半，而这题里答案的出现次数刚好是一半，和“不超过”的那个边界重叠了。用一个不满足前提的算法去解，结果可能是对的，也可能是错的，属于不能自洽的方案。第二个误区是排序后取nums[n]。前面已经说过，[1, 1, 2, 3]这种用例会让它当场翻车。如果非要走排序路线，扫一遍找相邻相等才是稳妥的写法。第三个误区是不够重视“其他元素互不相同”这个约束，把它当成无关紧要的废话。实际上，把这道题里的任何一条约束拿走，相邻比较法都不成立。比如把条件改成“数组中恰有一个元素出现 n 次”，但不管其他元素的重复次数，那数组里就可能有别的元素也出现多次，相邻比较查到的相等值未必是答案。到那时候，老老实实用哈希才是唯一稳定的解法。6.3 变体题与延伸思考顺着这个思路往下推，你可以自己设计一堆变体。比如“在长度为 3N 的数组中找出重复 N 次的元素”，这里答案占比三分之一，其他元素各出现一次。沿用抽屉原理，答案的两次出现之间的最大距离会变大，你需要检查的距离就不再只是 1 和 2 了，而是要根据总长度推算出一个安全距离。感兴趣的读者可以自己算一下，这比直接背代码更有收获。再比如把题目改成“数组长度为 2N，有一个元素出现 N+1 次，其余元素各出现一次”，这时答案出现次数超过一半，摩尔投票反而变得适用。你会发现两个看起来很相似的问题，因为一个数字的差异，最优解法就完全不同。这种“微调条件让解法改变”的敏感度，是刷题最值钱的能力。最后一个建议是，遇到这种带强约束条件的题目，别急着写代码，先在草稿纸上把条件翻译成“能推出什么”。我在实际刷题中发现，花两分钟做这个翻译，往往比多走几次调试更省时间。
这题我愿称之为“最容易被过度设计的简单题”。第一次在题库里翻到“在长度 2N 的数组中找出重复 N 次的元素”时，我脑子里冒出来的第一反应是：又要上哈希表数次数了。但等我耐着性子把题干里的三个条件逐条读完之后，才意识到这题考的根本不是数据结构的熟练度，而是你有没有把“约束条件”当成解题线索的习惯。如果你正在准备算法面试，或者正在刷数组类的题目，这题是个极好的“读题比写代码更重要”的案例。它的难度放在 LeetCode 里只能算简单偏下，但里面藏着的数学推导非常典型，适合刚接触刷题的新手用来建立“条件敏感度”，也适合有经验的人拿来反推自己是不是一上来就无脑哈希。整道题的代码量不超过十行，但是把“为什么能这么写”讲清楚，比AC二十道题都有用。1. 题目拆解：读懂“重复 N 次”背后的隐藏条件1.1 题干到底在说什么题目本身的表述非常克制，一共给了三条信息：数组长度是2 * n，偶数。数组里有n + 1个互不相同的元素。其中恰好有一个元素重复了n次，其余元素都只出现一次。最后要求你把这个重复了n次的元素找出来。很多人会忽略第二条里“互不相同”这四个字，但整道题能不能做到O(1)空间，靠的就是它。稍微翻译一下：既然总共有n + 1种不同的值，而数组长度是2n，那意味着这n + 1种值里，只有一种值的出现次数大于 1，其他每一种最多出现一次。又因为题目明说了“恰有一个元素重复n次”，所以剩下的n种值在数组里就是各出现一次，不多不少。这个结论看起来平淡，但它直接导出一个使用率极高的性质：只要在数组里看到某个值出现了第二次，这个值就一定是答案，不需要继续数下去。这个性质是所有“提前返回”解法的基础。1.2 这个条件能榨出什么信息我刷题时有个习惯：每读到一个条件，都会在草稿纸上写一下“这个条件能推出什么”。这题的三个条件放在一起，能推出的信息其实比表面看上去多得多。数组长度是2n，答案出现n次，说明答案的出现频率恰好是二分之一。但注意，它和“摩尔投票法”那类“出现次数超过一半”的题目有本质区别。超过一半意味着答案的数量比所有其他元素加起来还多，而这题里答案的数量只是和其他元素的数量打了个平手。所以如果你第一时间想到摩尔投票，这题大概率会翻车，后面我会专门说为什么。另一个能推出来的信息是：因为其他n个元素各不相同，它们之间永远不会产生“相邻相等”的情况，唯一会制造相邻重复的就只有答案本身。换句话说，一旦数组里出现了任何一对相邻或近邻相等的元素，这对元素一定和答案有关。这个观察是O(1)空间解法的核心线索。2. 解法一：哈希表计数，最稳妥也最容易想到的答案2.1 思路与代码实现先说最直接的暴力方案：遍历数组，用一个集合记录已经见过的值，遇到已经在集合里的值就直接返回。因为其他元素都是唯一的，所以第一个被重复访问到的值必然是答案。def repeatedNTimes(nums): seen = set() for num in nums: if num in seen: return num seen.add(num)这段代码可以说是“闭着眼都能写”的那种。我第一次做这题的时候也是这么写的，跑了一遍测试就过了。如果用 C++ 写，思路完全一样：class Solution { public: int repeatedNTimes(vector<int>& nums) { unordered_set<int> seen; for (int num : nums) { if (seen.count(num)) return num; seen.insert(num); } return -1; } };这里要注意一个细节：为什么“第一个重复出现的值”一定是答案，而不是其他元素？因为题目说了，除了答案以外的n个元素全部互不相同，它们在数组里只会出现一次，永远不会被第二次遇到。答案出现n次，且n至少为 2（否则题目就没意义了），所以遍历过程中答案一定会被第二次遇到，而其他元素不可能，因此第一次触发seen里已存在的值，必然是答案。2.2 复杂度分析与适用场景哈希解法的时间复杂度是O(n)，空间复杂度是O(n)，因为最坏情况下要把前n个不同元素都存进集合里才能遇到答案的第二次出现。这个解法在面试里完全可以作为“我想到了什么”的第一步回答。它正确、简洁、不容易出 bug。但说实话，如果面试官接下来问你“能不能把空间复杂度降到O(1)”，你就需要立刻意识到，题目里“其他元素互不相同”这个条件还没有被充分使用。这时候顺着条件往下挖，才有机会展示真正的解题能力。我自己在实际刷题复盘的时候，会刻意把哈希解法标记为“保底答案”，它的价值是让你先有正确解，再优化。如果你一上来就死磕最优解，卡住了连保底分都拿不到。面试也一样，先给能干活的方案，再讲更优雅的方案，观感会好很多。3. 解法二：排序后找相邻相等，思路简单但要注意陷阱3.1 思路与代码实现另一种不需要哈希表的办法是排序。排序之后，相同的值会聚在一起。因为答案是唯一出现多次的元素，排序后的数组里，有一整段长度为n的区域全是同一个值。在这个连续段内部，必然存在至少一对相邻相等的元素。扫描一遍排序后的数组，找到第一对相邻相等，返回即可。def repeatedNTimes(nums): nums.sort() for i in range(len(nums) - 1): if nums[i] == nums[i + 1]: return nums[i]这个写法看起来很干净，但这里藏着一个很多人会踩的坑。我见过不少题解在排序之后直接返回nums[n]，理由是“答案占了一半，排序后中间位置的元素肯定是答案”。这个结论在部分用例下是对的，但并不是恒成立的。举个例子，数组[1, 1, 2, 3]，n = 2，排序后还是[1, 1, 2, 3]，nums[n]也就是nums[2]是2，但答案是1。再比如[5, 1, 5, 2, 5, 3, 5, 4]，n = 4，排序后是[1, 2, 3, 4, 5, 5, 5, 5]，nums[4]是5，答案恰好对上了。也就是说，排序后取中位数能不能赢，完全取决于答案的连续段起始位置在哪里，不能靠赌。3.2 排序解法为什么不推荐在面试里当主力排序的时间复杂度是O(n log n)，空间复杂度取决于排序实现，Python 内置sort是额外O(n)，C++ 的std::sort在某些实现下也需要递归栈空间。从效率上讲，它比哈希解法和相邻比较法都差一截。更关键的是，排序没有利用“其他元素互不相同”这个核心条件。你会发现，就算去掉这个条件，排序后找相邻相等的做法在“答案恰好是唯一重复元素”的前提下依然能跑通。换句话说，排序解法把一道三个条件的题目，降维成了一个纯堆数据结构的题目，这本身就是对题面信息的浪费。所以我的建议是：排序解法适合用来做验证，比如在你的代码跑出来之后，写一段辅助逻辑核对答案是否正确。面试回答时，如果你先讲了哈希，又讲排序，面试官会觉得你有一定积累，但没有挖掘题目的独特点。真正的亮眼操作，是搬出下面这个相邻比较法。4. 解法三：相邻比较法，把空间压到 O(1)4.1 抽屉原理的直觉理解先建立直觉。假设答案元素是x，它在数组里出现了n次。如果x的任何两次出现之间都不相邻，那它至少得隔开多远？如果任意两次出现之间至少隔两个位置，也就是索引差至少为 3，那么n个x要占据的最小跨度是第 1 个到第n个之间的总长度。放最紧凑也得是0, 3, 6, 9, ...这样摆，最后一个x会在索引3 * (n - 1)的位置。数组总长度只有2n - 1个索引可用，想要3 * (n - 1) <= 2n - 1成立，算一下就知道n最多等于 2。换句话说，只要n >= 3，答案的n次出现里，就必然能找到一对索引差为 1 或 2 的。而索引差为 1 就是相邻，索引差为 2 就是隔一个元素。这就是为什么我们只需要检查这两种距离，就能覆盖绝大多数情况。那n = 2的时候呢？数组长度 4，答案出现 2 次。最极端的摆放是放在索引 0 和索引 3，距离 3，确实躲过了距离 1 和距离 2 的检查。但别忘了前面说的性质：其他元素都是唯一的，所以除了答案之外，索引 0 到 3 里剩下的两个位置填的是两个互不相同的元素。此时索引 0 的位置一定是答案，兜底返回nums[0]就能拿到正确结果。4.2 为什么检查间隔 1 和间隔 2 就足够为了把这个结论讲得更严谨，我用分组法再过一遍。把2n个索引按相邻两两分组：(0, 1), (2, 3), ..., (2n-2, 2n-1)，一共n组。现在考虑答案x在这n组里的分布情况。第一种情况，x在某一组内部出现了两次。同一组的两个索引是相邻的，检查间隔 1 时就会命中，直接返回。第二种情况，x在每一组里最多出现一次。因为总共只有n组，而x恰好出现n次，所以它必须在每一组里都出现一次。这时候看前两组：第一组(0, 1)和第二组(2, 3)。x在第一组里要么在0，要么在1；在第二组里要么在2，要么在3。把所有组合过一遍：x同时出现在 0 和 2，索引差 2，间隔 2 检查命中。x同时出现在 1 和 2，索引差 1，间隔 1 检查命中。x同时出现在 1 和 3，索引差 2，间隔 2 检查命中。x同时出现在 0 和 3，索引差 3，前两种检查都漏掉。但注意，这四种里只有最后一种会成为漏网之鱼，而这恰好意味着nums[0]就是答案。所以算法最后兜底返回nums[0]，靠的就是这个结论。4.3 代码实现与边界处理def repeatedNTimes(nums): total = len(nums) # 检查间隔为 1 的相邻元素 for i in range(total - 1): if nums[i] == nums[i + 1]: return nums[i] # 检查间隔为 2 的元素 for i in range(total - 2): if nums[i] == nums[i + 2]: return nums[i] # 兜底返回第一个元素 return nums[0]C++ 版本：class Solution { public: int repeatedNTimes(vector<int>& 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]; } };代码里有两个边界需要留意。第一个循环到n - 2为止，保证i + 1不越界。第二个循环到n - 3为止，保证i + 2不越界。我第一次手写的时候，第二段循环条件写成了n - 2，结果最后一个位置访问越界，排查了半天。这种“多走一位”的边界错误，在数组类算法题里太常见了，写的时候心里要清楚最后一对合法组合是哪两个索引。这个解法的时间复杂度是O(n)，因为两轮循环各扫一遍，常数系数也就是 2。空间复杂度是O(1)，只用了几个变量。在面试里，这个答案就是本题的最优解。5. 三种解法对比与面试打法5.1 复杂度与优缺点横向对比解法时间复杂度空间复杂度代码量是否利用题目核心条件风险点哈希集合O(n)O(n)极少部分利用容易被追问能否省空间排序 + 相邻查找O(n log n)O(n)（取决于实现）少基本没利用排序后取中位数可能踩坑相邻比较O(n)O(1)极少充分挖掘边界写错导致越界从表里能一眼看出，相邻比较法在时间、空间、代码量三个维度都是最优的。但我不建议你直接跳过前两种解法直接写最优解，因为面试考察的不仅是“能不能 AC”，还有“你的思考过程有没有逻辑层级”。5.2 面试时按什么顺序讲我自己复盘面试场景时，总结出的比较稳妥的打法是三步走。第一步先说暴力思路：“看到重复元素，天然会想到用哈希集合记录已经见过的值，碰到第二个见过的值直接返回，这个做法 O(n) 时间和 O(n) 空间。”这么说，代码还没写，面试官就知道你有基本的数据结构能力。第二步抛出问题：“这个解法能不能优化？我注意到题目里有一条特殊条件——除了答案以外的元素都互不相同。这意味着数组里一旦出现相邻的重复值，几乎可以断定是答案。于是我们可以检查间隔为 1 和间隔为 2 的元素，如果都没找到，再返回第一个元素。这个推导是严格成立的，空间能压到 O(1)。”第三步如果面试官追问“为什么间隔 1 和 2 就够了”，你就有机会把第四节的抽屉原理和分组法讲一遍。讲到这，整个回答的深度就出来了。这里有一个很现实的经验：很多候选人会在第一步和第二步之间卡住，因为他们不知道从哈希到 O(1) 的桥梁是什么。桥梁就是题干里那个“其他元素互不相同”的条件。刷题的时候多养成“翻译条件”的习惯，面试时自然就有话讲。6. 常见问题与排查技巧实录6.1 边界条件与特殊用例这题我在测试时发现，最容易出问题的其实是小数组，尤其是n = 2的情况。数组长度只有 4，比如[1, 2, 3, 3]，间隔 1 直接命中nums[2] == nums[3]，没问题。但如果测试用例是[1, 2, 3, 1]，答案1出现在索引 0 和索引 3，间隔为 3。这时候间隔 1 和间隔 2 都查不出来，算法会走到return nums[0]，也就是返回1，正确。另一个边界是极端分布[1, 2, 1, 2]这类。等等，这个用例里出现了两个重复元素，不符合题目“n+1 个不同元素”的前提，所以它根本不会出现在合法测试集里。我拿它测试只是因为想确认算法在非法输入下不会写出越界异常，这个从工程健壮性角度算一个加分项，但不是必须的。写单元测试的时候，我通常会覆盖几类典型场景：答案在数组开头连续出现：[3, 3, 1, 2]答案在数组末尾连续出现：[1, 2, 3, 3]答案均匀分布且首尾相隔最大：[1, 2, 3, 1]答案在中间隔一个位置：[2, 1, 2, 3]把这几个用例跑通，代码基本就稳了。6.2 这题最容易踩的三个认知误区第一个误区是直接套摩尔投票法。我见过不止一个人在讨论区里贴摩尔投票的代码，但它在这题里是错的。摩尔投票的前提是候选元素出现次数超过一半，而这题里答案的出现次数刚好是一半，和“不超过”的那个边界重叠了。用一个不满足前提的算法去解，结果可能是对的，也可能是错的，属于不能自洽的方案。第二个误区是排序后取nums[n]。前面已经说过，[1, 1, 2, 3]这种用例会让它当场翻车。如果非要走排序路线，扫一遍找相邻相等才是稳妥的写法。第三个误区是不够重视“其他元素互不相同”这个约束，把它当成无关紧要的废话。实际上，把这道题里的任何一条约束拿走，相邻比较法都不成立。比如把条件改成“数组中恰有一个元素出现 n 次”，但不管其他元素的重复次数，那数组里就可能有别的元素也出现多次，相邻比较查到的相等值未必是答案。到那时候，老老实实用哈希才是唯一稳定的解法。6.3 变体题与延伸思考顺着这个思路往下推，你可以自己设计一堆变体。比如“在长度为 3N 的数组中找出重复 N 次的元素”，这里答案占比三分之一，其他元素各出现一次。沿用抽屉原理，答案的两次出现之间的最大距离会变大，你需要检查的距离就不再只是 1 和 2 了，而是要根据总长度推算出一个安全距离。感兴趣的读者可以自己算一下，这比直接背代码更有收获。再比如把题目改成“数组长度为 2N，有一个元素出现 N+1 次，其余元素各出现一次”，这时答案出现次数超过一半，摩尔投票反而变得适用。你会发现两个看起来很相似的问题，因为一个数字的差异，最优解法就完全不同。这种“微调条件让解法改变”的敏感度，是刷题最值钱的能力。最后一个建议是，遇到这种带强约束条件的题目，别急着写代码，先在草稿纸上把条件翻译成“能推出什么”。我在实际刷题中发现，花两分钟做这个翻译，往往比多走几次调试更省时间。