如何降低检查数组重复元素代码的时间复杂度？

你的代码逻辑没问题，但双重循环的时间复杂度是O(n²)，当数组规模较大（比如n超过10^4）时，很容易触发超时。下面提供两种更高效的优化方案：

方案1：排序后检查相邻元素 #

先对数组进行排序，排序的时间复杂度为O(n log n)，之后只需一次遍历（O(n)）检查相邻元素是否相等即可。整体时间复杂度为O(n log n)，C标准库的qsort是原地排序，空间复杂度仅为O(log n)。

示例代码：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// qsort 所需的整数比较函数
int compareInts(const void *a, const void *b) {
    return *(int*)a - *(int*)b;
}

bool containsDuplicate(int *nums, int numsSize) {
    if (numsSize <= 1) return false;
    
    qsort(nums, numsSize, sizeof(int), compareInts);
    
    for (int i = 0; i < numsSize - 1; i++) {
        if (nums[i] == nums[i+1]) {
            return true;
        }
    }
    return false;
}

方案2：使用哈希表（平均O(n)时间复杂度） #

利用哈希表的O(1)平均查找/插入特性，遍历数组时：

• 若当前元素已在哈希表中，直接返回true
• 若不存在，将元素插入哈希表

C标准库没有内置哈希表，可使用第三方库（如uthash）或自定义哈希结构。以下是基于uthash的示例（需引入uthash.h）：

#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) {
            // 找到重复，释放哈希表内存后返回
            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);
    }
    // 无重复，释放哈希表内存
    HashItem *item, *tmp;
    HASH_ITER(hh, hashTable, item, tmp) {
        HASH_DEL(hashTable, item);
        free(item);
    }
    return false;
}

方案对比 #

• 排序方案：无额外依赖，空间开销小，但会修改原数组。
• 哈希表方案：平均时间效率更高（O(n)），但需要额外空间，依赖第三方库或自定义实现，不会修改原数组。

内容的提问来源于stack exchange，提问作者hara sahiti vemuru