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

接上文，我们来看第二中解决方案：

方法二：数学

思路与算法

我们可以考虑重复的元素 x 在数组 nums 中出现的位置。如果相邻的 x 之间至少都隔了 2 个位置，那么数组的总长度至少为：

当 n > 2 时，3n−2 > 2n ，不存在满足要求的数组。因此一定存在两个相邻的 x ，它们的位置是连续的，或者只隔了 1 个位置。

当 n=2 时，数组的长度最多为 2n=4 ，因此最多只能隔 2 个位置。

这样一来，我们只需要遍历所有间隔 2 个位置及以内的下标对，判断对应的元素是否相等即可。

代码

C++

class Solution { public: int repeatedNTimes(vector<int>& nums) { int n = nums.size(); for (int gap = 1; gap <= 3; ++gap) { for (int i = 0; i + gap < n; ++i) { if (nums[i] == nums[i + gap]) { return nums[i]; } } } // 不可能的情况 return -1; } };

Java

class Solution { public int repeatedNTimes(int[] nums) { int n = nums.length; for (int gap = 1; gap <= 3; ++gap) { for (int i = 0; i + gap < n; ++i) { if (nums[i] == nums[i + gap]) { return nums[i]; } } } // 不可能的情况 return -1; } }

C#

public class Solution { public int RepeatedNTimes(int[] nums) { int n = nums.Length; for (int gap = 1; gap <= 3; ++gap) { for (int i = 0; i + gap < n; ++i) { if (nums[i] == nums[i + gap]) { return nums[i]; } } } // 不可能的情况 return -1; } }