最近看到Leecode上一道重复检测问题，中间尝试了几种实现方案记录如下。

给定一个整数数组，判断是否存在重复元素。

如果任何值在数组中出现至少两次，函数返回 true。如果数组中每个元素都不相同，则返回 false。

示例 1:

输入: [1,2,3,1]

输出: true

示例 2:

输入: [1,2,3,4]

输出: false

示例 3:

输入: [1,1,1,3,3,4,3,2,4,2]

输出: true

排序 + 查找

选择排序

bool containsDuplicate(int* nums, int numsSize) {    int i, j, min, p;    for ( i = 0; i < numsSize; i++) {        min = nums[i];        p = i;        for (j = i + 1; j < numsSize; j++) {            if(nums[j] == min)                return true;            else if(nums[j] < min) {                min = nums[j];                p = j;            }        }        if(p != i) {            nums[j] = nums[i];            nums[i] = min;        }    }    return false;}

实现比较简单，由于查找直接合并在排序当中，所以实际的时间复杂度与选择排序持平，时间复杂度o(n^2)。

不出意外，超时。emmmmmm

快速排序

在网上查了一下其他人的搜索方案，Java 有直接使用Arrays.sort方法通过的。

看了一下JDK的源码，java这块其实就是快拍的实现。时间复杂度(log n)。

哈希

静态hash

之前以为int 型还是 75536呢，直接生成 75536长度的bool 数组，命中直接置为true。后来发现现在已经是 2^32 了。

动态hash

AC 通过数组链表来实现动态hash匹配，最坏情况时间复杂度 log n

bool hashMatch(int* nums, int numsSize) {    int i, j, temp;    int** hashTable = NULL;    int hashSize = (int)sqrt(numsSize) + 1;    hashTable = (int **)malloc(sizeof(int*) * hashSize);    for(i = 0; i< hashSize; i++) {        hashTable[i] = (int *)malloc(sizeof(int) * hashSize);    }    for(i = 0; i < hashSize; i++) {        for(j = 0 ; j< hashSize; j++) {            hashTable[i][j] = -1;        }    }    for(i = 0; i < numsSize; i ++) {        if(nums[i] < 0)            temp = (-nums[i]) % hashSize;        else            temp = nums[i] % hashSize;        for(j = 0; j < hashSize; j++) {             if(hashTable[temp][j] == -1) {                hashTable[temp][j] = i;                break;             } else if(nums[hashTable[temp][j]] == nums[i])                return true;        }    }    return false;}