如何不使用嵌套循环查找两个数组中的重复元素

你原本的双层循环实现时间复杂度为O(mn)*，数组量级较大时运行耗时会大幅提升，以下两种方案均可去掉双层嵌套循环，大幅提升运行效率：

方案1：哈希集合查询法 #

时间复杂度O(m + n)，空间复杂度O(min(m,n))
核心思路是先将长度更短的数组存入哈希集合/哈希表，再遍历另一个数组，单次判断元素是否存在的时间复杂度为O(1)，仅需要两次单层循环即可完成遍历。
示例实现（类C语法）：

// 优先把长度更小的数组存入集合，节省空间
HashSet set = createHashSet(n);
for(j = 0; j < n; j++){
    addToSet(set, arr2[j]);
}

// 遍历第二个数组逐一判断
for(i = 0; i < m; i++){
    if(contains(set, arr1[i])){
        // 匹配到重复元素的逻辑
    } else {
        // 未匹配到重复元素的逻辑
    }
}

如果需要统计同一元素的重复出现次数，将哈希集合替换为键存元素、值存出现次数的哈希表即可。

方案2：排序+双指针法 #

时间复杂度O(mlogm + nlogn)，空间复杂度O(1)（不计排序算法的额外空间开销）
如果对空间占用有严格要求，可以选用该方案：先对两个数组分别做升序排序，再用两个指针同步遍历两个数组匹配重复元素。
示例实现（类C语法）：

// 对两个数组分别排序
sort(arr1, m);
sort(arr2, n);

int i = 0, j = 0;
while(i < m && j < n){
    if(arr1[i] == arr2[j]){
        // 匹配到重复元素的逻辑
        i++;
        j++;
    } else if(arr1[i] < arr2[j]){
        // arr1当前元素更小，移动i指针
        // 未匹配逻辑可在此处执行
        i++;
    } else {
        // arr2当前元素更小，移动j指针
        // 未匹配逻辑可在此处执行
        j++;
    }
}

// 处理剩余未遍历的无匹配元素，按需执行未匹配逻辑
while(i < m){
    i++;
}
while(j < n){
    j++;
}

• 注意：该方案会改变原数组的元素顺序，如果需要保留原数组顺序，需先拷贝数组再执行排序操作。

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