【题目描述】
给定一个长度为 n 的整数数组 nums，数组中所有的数字都在 0 ∼ n−1 的范围内。
数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。
请找出数组中任意一个重复的数字。
注意：如果某些数字不在 0 ∼ n−1 的范围内，或数组中不包含重复数字，则返回 -1；
样例
给定 nums = [2, 3, 5, 4, 3, 2, 6, 7]。
返回 2 或 3。
【算法描述】
数组中的数的范围在 0 ∼ n−1是解题思路的核心。
遍历整个数组，将数组中数放在对应的位置上即nums[i] = i，也就是说每一个数都放在了自己对应的位置上，如果有一个数x重复的话则会出现这个数与对应的数组下标不相等即x != i，并且将该数作为数组下标得到的数也为该数即num[x] == x。
整体思路如上所示，具体算法如下：
因为数组有可能出现 0 ∼ n−1范围外的数，所以首先对数组进行遍历，如果数组中的数x < 0或者x >= n则直接返回-1；
同样从前往后遍历数组，比如遍历到nums[i] = x时：
-
如果
x != i并且nums[x] = x则直接返回nums[i]，表示已经找到重复的数 -
如果
nums[x] != x，此时需要将x放在对应的位置上，将当前位置上的数x放到以x为数组下标的位置即swap(nums[i], nums[x])。循环执行上述操作，直到将当前位置上的数放在其对应的位置上。
执行完上述操作如果还没找到重复的数直接返回-1。
【时间复杂度分析】
首先会遍历一遍数组判断数组中是否有不在0~n-1范围内的数，所需时间复杂度为O(N)；
每次swap会将一个数放在正确的位置，最后一次swap会将两个数分别放在正确的位置上，n个数就有n个位置，swap操作最多执行n-1次，所以总的时间复杂度为O(N)。
【代码示例】
class Solution {
public:
int duplicateInArray(vector<int>& nums) {
int n = nums.size();
for (auto x : nums)
{
if (x < 0 || x >= n) return -1;
}
for (int i = 0; i < n; i++)
{
while (nums[nums[i]] != nums[i]) swap(nums[nums[i]], nums[i]);
if (nums[i] != i && nums[nums[i]] == nums[i]) return nums[i];
}
return -1;
}
};