C++中快速判断两个vector是否存在公共元素的高效方法

双层遍历逐元素比对的时间复杂度是O(n*m)（n、m为两个vector的长度），数据量稍大时效率很低，确实存在更优的实现方案。

你提出的「合并插入set比较大小」思路评估 #

这个思路逻辑上有硬伤，且性能不是最优，不推荐直接使用，问题主要有三点：

• 存在误判可能：如果单个vector内部存在重复元素，哪怕两个vector完全没有交集，插入set后的总大小也会小于两个vector的长度和，直接返回错误结果。

反例：vec1为{{'c'},{'c'}}、vec2为{{'a'},{'b'}}时，两个vector无公共元素，但所有元素插入set后大小为3，小于两vector长度和4，按该逻辑会误判存在公共元素。

• 无法利用「仅判断存在性」的特性做提前终止：必须把两个vector所有元素都插入set才能做大小比较，哪怕第一个元素就是公共元素，也要处理完全部数据，浪费算力。
• 内存开销更高：需要存储两个vector的全部元素，内存占用比最优方案高近一倍。

推荐实现方案 #

最优思路的时间复杂度最低可以到平均O(n+m)，核心逻辑是：

1. 优先选择长度更短的vector，把它的所有元素存入集合（自动去重），尽可能降低建集合的开销。
2. 遍历另一个vector的元素，每拿到一个元素就判断是否在刚才的集合中：只要找到一个存在的元素，立刻返回true（存在公共元素），不需要处理后续元素。
3. 如果遍历完所有元素都没命中集合，返回false。

针对你使用的vector<vector<char>>元素类型，有两个落地选择：

• 开箱即用方案：用C++标准库的set<vector<char>>做存储结构。vector本身默认支持字典序比较，可以直接作为set的键，不需要额外写适配逻辑，时间复杂度为O(min(n,m)logmin(n,m) + k*logmin(n,m))（k是遍历到第一个公共元素时走过的元素个数，最坏情况是m），绝大多数场景下性能足够。
• 极致性能方案：自定义vector<char>的哈希函数，用unordered_set做存储，平均时间复杂度为线性O(n+m)，适合数据量极大的场景。

参考实现代码（开箱即用版） #

#include <vector>
#include <set>
using namespace std;

bool hasCommon(const vector<vector<char>>& a, const vector<vector<char>>& b) {
    // 始终用更短的vector建集合，压缩开销
    if (a.size() > b.size()) return hasCommon(b, a);
    set<vector<char>> checkSet(a.begin(), a.end());
    for (const auto& elem : b) {
        // 找到第一个公共元素直接返回，提前终止
        if (checkSet.count(elem)) return true;
    }
    return false;
}

针对你给出的测试用例：

vector<vector<char>> vec1 = {{'a','b'}, {'c'}};
vector<vector<char>> vec2 = {{'a'},{'b'},{'c'}};

调用hasCommon(vec1, vec2)时，遍历到vec2中的{'c'}就会命中集合，直接返回正确结果true。

补充说明：如果两个vector的长度都极小（比如长度均小于10），双层遍历因为没有建集合的常数开销，实际运行速度可能反而更快，这种场景可以直接用双层遍历，不需要引入集合结构。

内容的提问来源于stack exchange，提问作者Dave Brown