在长度2N的数组中找出重复N次的元素（二）

接上文我们来看解决方案思路和算法记重复 n 次的元素为 x 。由于数组 nums 中有 n1 个不同的元素而其长度为 2n 那么数组中剩余的元素均只出现了一次。也就是说我们只需要找到重复出现的元素即为答案。因此我们可以对数组进行一次遍历并使用哈希集合存储已经出现过的元素。如果遍历到了哈希集合中的元素那么返回该元素作为答案。代码Cclass Solution { public: int repeatedNTimes(vectorint nums) { unordered_setint found; for (int num: nums) { if (found.count(num)) { return num; } found.insert(num); } // 不可能的情况 return -1; } };Javaclass Solution { public int repeatedNTimes(int[] nums) { SetInteger found new HashSetInteger(); for (int num : nums) { if (!found.add(num)) { return num; } } // 不可能的情况 return -1; } }C#public class Solution { public int RepeatedNTimes(int[] nums) { ISetint found new HashSetint(); foreach (int num in nums) { if (!found.Add(num)) { return num; } } // 不可能的情况 return -1; } }Python3class Solution: def repeatedNTimes(self, nums: List[int]) - int: found set() for num in nums: if num in found: return num found.add(num) # 不可能的情况 return -1复杂度分析时间复杂度O(n) 。我们只需要对数组 nums 进行一次遍历。空间复杂度O(n) 即为哈希集合需要使用的空间。