官方题解给了个双指针的方法，估计面试也不会，先不看了。
正常方法：
1.排序
2.用set或者直接在原vector上记录出现的值
3.二分，这里是对数据范围2分。令n为vector长度，则所有数据都在1到n-1的范围内。取le=1，ri=n-1，mi=n/2。然后遍历整个vector，计算在[le,mi]或者[mi+1,ri]的范围内出现的数字次数。比如计算[le,mi]范围内数字出现的次数大于mi-le+1，说明[le,mi]范围内的数字一定至少有一个是不止出现一次的。
1 class Solution { 2 public: 3 int findDuplicate(vector<int>& nums) 4 { 5 int left=1,right=nums.size()-1; 6 while(left<right) 7 { 8 int mid=left+(right-left+1)/2; 9 int count=0; 10 for (auto num:nums) 11 { 12 if(num<=right and num>=mid) 13 { 14 ++count; 15 } 16 } 17 if(count<=right-mid+1) 18 { 19 right=mid-1; 20 } 21 else 22 { 23 left=mid; 24 } 25 } 26 return left; 27 } 28 };
原文：https://www.cnblogs.com/FdWzy/p/12289492.html