给定一个长度为 n 的整数数组 nums，数组中所有的数字都在 0∼n−1的范围内。
数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。
请找出数组中任意一个重复的数字。
注意：如果某些数字不在 0∼n−1 的范围内，或数组中不包含重复数字，则返回 -1；
最优方法：时间复杂度为O（N），空间复杂度为O（1）；
利用数值在0-n-1范围内，有些像鸽洞原理；
class Solution { public: int duplicateInArray(vector<int>& nums) { for(auto x:nums) if(x < 0 || x >=nums.size()) return -1; for(int i = 0;i < nums.size(); i++){ while(nums[i] != i && nums[nums[i]] != nums[i]) //不在正确的位置 && 交换地方也不是正确的位置 swap(nums[i],nums[nums[i]]); if(nums[i]!= i) //因为正常情况下，nums[i]是会在正确的位置 return nums[i]; } return -1; } };
原文：https://www.cnblogs.com/Aliencxl/p/12325418.html