java - 两个数字 x 和 y 来自两个不同的数组。查找是否存在满足 z= x+y 的和 z

Question

需要补充的是，每个数组中有n个整数，每个整数都在0到n^5之间。有没有办法用线性时间算法解决这个问题？

Answer 1

是的，在这些假设下，线性时间是可能的:

• 您的输入是(例如)32 位整数数组。
• 两个整数相加的复杂度为 O(1)。
• 你的机器有无限的内存，读取内存中任何地方的一个字节是一个 O(1) 操作。

1) 将其中一个数组转换为哈希集，查找时间复杂度约为 O(1)。哈希集的构建大约需要线性时间。

2) 遍历另一个数组，对于每个元素 i，检查 x - i 是否在哈希集中。如果匹配则 (i, x - i) 是一个解决方案。此步骤需要线性时间。