如何编写时间复杂度O(n)的伪代码判断两数组是否有公共元素

你当前的嵌套循环确实是O(n²)的时间复杂度，要优化到O(n)级别，最直接的方法是借助哈希集合，利用集合的O(1)查找特性。如果想基于排序实现，虽然时间达不到严格的O(n)，但也是远优于O(n²)的优化方案，下面分别给出两种可行方案：

方案一：哈希集合法（时间O(n+m)，空间O(n)） #

伪代码 #

function hasCommonElement(A, B):
    创建空哈希集合 set
    遍历数组A的每个元素element:
        将element加入set
    遍历数组B的每个元素element:
        若element存在于set中:
            返回true
    返回false

说明 #

• 遍历A构建集合的时间为O(n)（n为A的长度），遍历B查找的时间为O(m)（m为B的长度），总时间复杂度为O(n+m)，当n和m规模相近时等价于O(n)。
• 空间复杂度取决于A的元素数量，为O(n)，用于存储A的所有元素。

方案二：排序+双指针法（时间O(n log n + m log m)，空间O(1)或O(n+m)） #

如果你想基于排序实现，核心逻辑是先对两个数组排序，再用双指针同步遍历，避免嵌套循环：

伪代码 #

function hasCommonElement(A, B):
    对数组A进行排序
    对数组B进行排序
    初始化指针i = 0, j = 0
    当i < A.length 且 j < B.length:
        若A[i] == B[j]:
            返回true
        否则若A[i] < B[j]:
            i += 1  // 移动A的指针，寻找更大的元素
        否则:
            j += 1  // 移动B的指针，寻找更大的元素
    返回false

说明 #

• 排序阶段的时间为O(n log n + m log m)，双指针遍历阶段为O(n+m)，总时间复杂度为O(n log n + m log m)，远低于O(n²)。空间开销取决于排序方式：若使用原地排序（如堆排序），空间复杂度为O(1)；若使用非原地排序（如归并排序），空间复杂度为O(n+m)。

方案选择建议 #

• 若追求极致时间效率、内存充足，优先选哈希集合法。
• 若内存资源紧张，可选择排序+双指针法，以少量时间开销换取更低空间占用。

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