哈希，时间复杂度O(n)，空间复杂度O(n)，适用范围更广。

思路：

    哈希存入，查找是否存在，查找过程时间复杂度O(1)

#include <unordered_map>
class Solution {
public:
	bool duplicate(int numbers[], int length, int* duplication) {
		unordered_map<int, int> hash_map;
		for (int i = 0; i < length; i++) {
			auto it = hash_map.find(numbers[i]);
			if (it != hash_map.end()) {  //found
				*duplication = numbers[i];
				return true;
			}
			else {  //not found
				hash_map[numbers[i]] = i;
			}
		}
		return false;
	}
};

二、拿现有数组作查找log

        时间复杂度O(n)，空间复杂度O(1)，只适用于这些数都小于n的情况

思路：

        所有数都在n内，找第一组重复的值。
        那么在第一组重复的值的第二个值之前，所有的数字都只出现了一次。
        
        每遇到一个数x，都把以 x 为下标的数 array[x] + n，由于x不重复，以x为下标的元素也是不重复的
        当然，这样会把后面路上的元素+n，所以在考虑遇到的x时，如果 x>n 要将 x-=n ，减的是副本，所以不影响找到目标。
        当重复时，即想把一个数+n时，发现它已经>n了，这就是第一组。
        
        最终效果就是：
            突出的元素（+n）就代表已经已经出现过，用来当访问记录log。把从哈希表中查找，转换到了在本数组查找
        
        改进点：
            x + n，如果 n > INT_MAX/2 就可能会导致溢出
            
            改成 x - n ：
                假设n = INT_MAX
                [0 , INT_MAX - 1]  --->  [-INT_MAX , -1]，既不溢出，也没有歧义

class Solution {
public:
    bool duplicate(int numbers[], int length, int* duplication) {
        for(int i = 0; i < length; i++){
            int value = numbers[i];
            if(value < 0)  //路上被减小了的元素
                value += length;    //对副本操作，不影响找到目标
            if(numbers[value] < 0){    //发现以value为下标的数已经小于0了，表示这是已经访问过的。
                *duplication = value;
                return true;
            }
            numbers[value] -= length;  //去以value为下标的位置，-length
        }
        return false;
    }
};