数组中重复的数字
C++，原数组进行hash。
题目中说明了数字范围是[0, length - 1]就很明显有让原数组hash的意思了。
可以把被访问过这一信息，直接用原数组记录，具体方法我想到两种，假设当前访问到t = numbers[i]：
- numbers[t] += length;
- numbers[t] = -numbers[t]；
下次再碰到同样为t的值时，只要看是不是大于n或者是负数就行了。
class Solution {
public:
// Parameters:
// numbers: an array of integers
// length: the length of array numbers
// duplication: (Output) the duplicated number in the array number
// Return value: true if the input is valid, and there are some duplications in the array number
// otherwise false
bool duplicate(int numbers[], int length, int* duplication) {
for (int i = 0; i < length; i++) {
int t = numbers[i];
if (t >= length) t -= length;
if (numbers[t] >= length) {
*duplication = t;
return true;
}
numbers[t] += length;
}
return false;
}
};
