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

接上文我们来看第二中解决方案方法二数学思路与算法我们可以考虑重复的元素 x 在数组 nums 中出现的位置。如果相邻的 x 之间至少都隔了 2 个位置那么数组的总长度至少为当 n 2 时3n−2 2n 不存在满足要求的数组。因此一定存在两个相邻的 x 它们的位置是连续的或者只隔了 1 个位置。当 n2 时数组的长度最多为 2n4 因此最多只能隔 2 个位置。这样一来我们只需要遍历所有间隔 2 个位置及以内的下标对判断对应的元素是否相等即可。代码Cclass Solution { public: int repeatedNTimes(vectorint 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; } };Javaclass 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; } }