两无序数组求和为x的配对Java代码时间复杂度及伪代码咨询

1. 代码时间复杂度 #

这段基于哈希实现的算法平均时间复杂度为 O(n + m)，其中 n 是第一个数组arr1的长度，m 是第二个数组arr2的长度：

• 第一步遍历arr1的所有元素存入HashMap，哈希表的单元素插入操作平均耗时O(1)，该阶段总耗时O(n)
• 第二步遍历arr2的所有元素，计算目标补值（x减去当前元素）后查询哈希表是否存在，哈希表单元素查询操作平均耗时O(1)，该阶段总耗时O(m)
• 极端情况下如果出现大量哈希冲突，时间复杂度会升高，但JDK的HashMap内置了红黑树优化冲突场景，工程实践中基本可以稳定达到线性时间复杂度。

2. 对应伪代码 #

和Java实现逻辑完全对齐的伪代码如下：

// 输入：两个无序无重复元素数组arr1、arr2，arr1长度n，arr2长度m，目标和x
// 输出：所有分别来自两个数组、和为x的元素对
FUNCTION findPairs(arr1, arr2, n, m, x)
    // 初始化哈希表存储arr1的所有元素
    INIT hash_map = empty HashMap
    FOR i FROM 0 TO n-1
        hash_map[arr1[i]] = 0 // 值无实际意义，仅占位
    END FOR

    // 遍历arr2查找匹配的元素对
    FOR j FROM 0 TO m-1
        complement = x - arr2[j]
        IF complement EXISTS IN hash_map.keys
            PRINT complement + " " + arr2[j]
        END IF
    END FOR
END FUNCTION

注：原Java代码中HashMap的value无实际作用，实际实现时可替换为HashSet存储arr1元素，空间占用更低，逻辑完全一致。

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