题目描述
这是 LeetCode 上的 961. 在长度 2N 的数组中找出重复 N 次的元素 ，难度为 简单。
Tag : 「模拟」、「计数」、「构造」、「哈希表」
给你一个整数数组 nums ，该数组具有以下属性：
$nums.length == 2 \times n$
nums 包含 $n + 1$ 个 不同的 元素
nums 中恰有一个元素重复 $n$ 次
找出并返回重复了 $n$ 次的那个元素。
示例 1：
输入：nums = [1,2,3,3]输出：3
示例 2：
输入：nums = [2,1,2,5,3,2]输出：2
示例 3：
输入：nums = [5,1,5,2,5,3,5,4]输出：5
提示：
$2 <= n <= 50004
$nums.length == 2 \times n$
$0 <= nums[i] <= 10^4$
nums 由 $n + 1$ 个 不同的 元素组成，且其中一个元素恰好重复 $n$ 次
计数模拟
根据题目给定的三个条件可推断出：数组中仅有一个元素出现多次，其余元素均出现一次。
又利用数据范围为 $10^4$，我们可以使用数组充当哈希表进行计数，当出现一个 $nums[i]$ 重复出现即是答案。
代码：
class Solution { int[] cnts = new int[10010]; public int repeatedNTimes(int[] nums) { for (int x : nums) { if (++cnts[x] > 1) return x; } return -1; }} 时间复杂度：$O(n)$
空间复杂度：$O(C)$
构造共性
假设重复出现的数字是 $x$，数字 $x$ 重复了 $n$ 次，要将这 $n$ 个相同的 $x$ 间隔开，需要 $n - 1$ 个额外数字，而实际上我们除 $x$ 以外还有 $n$ 个额外数字（数字总数为 $n + 1$ 个），因此在我们所能构造出的所有排列方式中，最多 使相邻 $x$ 之间间隔了 $2$ 个额外数字。
对于每个 $nums[i]$ 而言，我们检查往前的三个位置（若有），如果有重复相等情况，说明当前的 $nums[i]$ 即是答案。
代码：
class Solution { public int repeatedNTimes(int[] nums) { int n = nums.length; for (int i = 0; i < n; i++) { int t = nums[i]; if (i - 1 >= 0 && nums[i - 1] == t) return t; if (i - 2 >= 0 && nums[i - 2] == t) return t; if (i - 3 >= 0 && nums[i - 3] == t) return t; } return -1; }} 时间复杂度：$O(n)$
空间复杂度：$O(1)$
最后
这是我们「刷穿 LeetCode」系列文章的第 No.961 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
原文：https://juejin.cn/post/7099999370413604894