在小于 O(n^2) 的时间内比较两个数组的元素？

Question

我有两个整数数组。我需要找出两个数字，每个数组中一个，其总和等于 2。这在 O(n^2) 中非常简单，但是有没有办法更快呢？

Answer 1

您可以在 O(N+M) 时间和 O(N) 空间内完成此操作，如下所示：

• 将数组的元素放a入哈希集
• 遍历数组b，并检查哈希表是否包含2-b[i]

构造元素的哈希集N需要 O(N) 时间和 O(N) 空间。根据哈希集检查每个M元素需要 O(1)，总共需要 O(N+M) 时间。