在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

法1：哈希表，时间复杂度On，空间复杂度On

bool duplicate(int numbers[], int length, int* duplication) {
	unordered_map<int, int> unmp;
	unmp.reserve(length);
	for (int i = 0; i < length; ++i) {
		if (unmp.find(numbers[i]) == unmp.end()) {
			unmp.insert({ numbers[i],1 });
		}
		else
		{
			*duplication = numbers[i];
			return true;
		}
	}
	return false;
}

法2：维护索引表

理解起来有点困难，最好是自己模拟一下过程。
可以参考下面这段，leetcode评论：

这个原地交换法就相当于分配工作，每个索引代表一个工作岗位，每个岗位必须专业对口，既0索引必须0元素才能上岗。而我们的目的就是找出溢出的人才，既0索引岗位有多个0元素竞争。
我们先从0索引岗位开始遍历，首先我们看0索引是不是已经专业对口了，如果已经专业对口既nums[0]=0，那我们就跳过0岗位看1岗位。如果0索引没有专业对口，那么我们看现在0索引上的人才调整到他对应的岗位上，比如num[0]=2，那我们就把2这个元素挪到他对应的岗位上既num[2]，这个时候有两种情况:1、num[2]岗位上已经有专业对口的人才了，既num[2]=2，这就说明刚刚那个在num[0]上的2是溢出的人才，我们直接将其返回即可。2、num[2]上的不是专业对口的人才，那我们将num[0]上的元素和num[2]上的元素交换，这样num[2]就找到专业对口的人才了。之后重复这个过程直到帮num[0]找到专业对口的人才，然后以此类推帮num[1]找人才、帮num[2]找人才，直到找到溢出的人才。

class Solution {
public:
    int findRepeatDocument(vector<int>& documents) {
        int i = 0;
        while(i < documents.size()){
            if(documents[i] == i){ // 如果索引与值相等
                i++;
                continue;
            }
            if(documents[documents[i]] == documents[i]){ // 如果找到了重复的索引
                // 有点递归的感觉 判断的是假如出现documents[2] = 2 和 documents[3] = 2 那么说明已经有重复的索引了 
                return documents[i];
            }else{
                // 例如 2 5 3, 当i=0时
                int tmp = documents[i];  // documents[i] = 2 = tmp
                documents[i] = documents[tmp];  // documents[i] = documents[2] = 3
                documents[tmp] = tmp; // 最后就可以得到 documents[2] = 2 把2这块的索引维护好了
            }
        }
        return -1;
    }
};