求C语言下更优的数组重复元素检测算法（期望O(n)时间复杂度）

原双重循环实现的时间复杂度为O(n²)，数据量较大时嵌套比对会导致性能急剧下降。要达到O(n)时间复杂度，核心思路是利用哈希表平均O(1)的查找、插入特性。

基于哈希表的C语言实现 #

C标准库没有内置哈希表，这里用C领域常用的轻量哈希库uthash实现：

#include <stdbool.h>
#include "uthash.h"

// 定义哈希表节点结构
typedef struct {
    int key;
    UT_hash_handle hh;
} HashItem;

bool containsDuplicate(int* nums, int numsSize) {
    HashItem *hashTable = NULL;
    for (int i = 0; i < numsSize; i++) {
        HashItem *item;
        // 查找当前元素是否已在哈希表中
        HASH_FIND_INT(hashTable, &nums[i], item);
        if (item != NULL) {
            // 找到重复元素，清理哈希表后返回true
            HashItem *tmp;
            HASH_ITER(hh, hashTable, item, tmp) {
                HASH_DEL(hashTable, item);
                free(item);
            }
            return true;
        }
        // 元素不在表中，插入哈希表
        item = (HashItem*)malloc(sizeof(HashItem));
        item->key = nums[i];
        HASH_ADD_INT(hashTable, key, item);
    }
    // 遍历完无重复，清理哈希表后返回false
    HashItem *item, *tmp;
    HASH_ITER(hh, hashTable, item, tmp) {
        HASH_DEL(hashTable, item);
        free(item);
    }
    return false;
}

关于“跳过已检查过的重复值”的问题 #

上述哈希表方案已经天然实现了跳过重复检查的逻辑：

• 首次处理某个元素时，会将其存入哈希表；
• 后续再遇到相同元素，哈希表查找会直接命中，此时立即返回true，不会再对该元素做重复比对；
• 已存入哈希表的元素无需二次处理，只要后续出现重复就会被立刻检测到，不需要额外的跳过逻辑。

如果不想依赖第三方库，也可以先对数组排序（时间复杂度O(nlogn)，实际性能接近O(n)），再遍历检查相邻元素是否重复，但这种方式的时间复杂度略高于哈希表方案。

内容的提问来源于stack exchange，提问作者Anshul Patel