C++中检测长int数组是否存在重复元素的最快方法是什么？

针对极长int数组的重复检测，根据不同的约束条件，有三种性能优异的方案可选，均远优于O(n²)的暴力嵌套遍历：

1. 位图/布尔数组方案（性能天花板，适用元素范围有限场景） #

如果数组元素的取值范围可控（例如所有元素为非负整数，且最大值不超过1e7级别），该方案是最优选择，时间复杂度O(n)，空间复杂度O(maxVal)，无额外计算开销，访问完全连续缓存友好。

示例代码： #

#include <vector>
bool has_duplicate(const std::vector<int>& arr, int max_element_val) {
    std::vector<bool> visited(max_element_val + 1, false);
    for (int num : arr) {
        if (visited[num]) return true;
        visited[num] = true;
    }
    return false;
}

2. 排序后相邻校验方案（性能最稳定，适用允许修改原数组场景） #

如果元素取值范围不确定，但允许修改原数组，优先选择该方案，时间复杂度O(nlogn)，空间复杂度O(1)（原地排序无额外空间开销）。STL的std::sort做了高度优化，且连续内存访问缓存命中率极高，实际运行性能通常比哈希方案更稳定，不会出现哈希冲突导致的最坏情况。

示例代码： #

#include <vector>
#include <algorithm>
bool has_duplicate(std::vector<int>& arr) {
    if (arr.size() <= 1) return false;
    std::sort(arr.begin(), arr.end());
    for (size_t i = 1; i < arr.size(); ++i) {
        if (arr[i] == arr[i - 1]) return true;
    }
    return false;
}

如果不允许修改原数组，需要额外复制一份数组，此时空间复杂度变为O(n)，性价比低于哈希方案。

3. 哈希集合方案（适用不允许修改原数组、元素范围不确定场景） #

该方案平均时间复杂度O(n)，空间复杂度O(n)，不需要修改原数组，适用场景最广泛。注意需要预分配集合空间避免扩容开销，进一步提升性能。

示例代码： #

#include <vector>
#include <unordered_set>
bool has_duplicate(const std::vector<int>& arr) {
    std::unordered_set<int> visited;
    visited.reserve(arr.size()); // 预分配空间，避免多次扩容损耗性能
    for (int num : arr) {
        if (visited.count(num)) return true;
        visited.insert(num);
    }
    return false;
}

内容的提问来源于stack exchange，提问作者new Q Open Wid