两个数字 x 和 y 来自两个不同的数组。查找是否存在 z 之和使得 z= x+y
我需要补充一点，每个数组中有n个整数，每个整数都在0到n^5之间。线性时间算法有没有办法解决这个问题？
I need to add that there are n integers in each array, and each integer is between 0 and n^5. Is there any way to solve this problem in linear-time algorithm?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
是的，在这些假设下，在线性时间内是可能的：
1) 将其中一个数组转换为哈希集，查找时间复杂度约为 O(1)。哈希集的构造大约需要线性时间。
2) 迭代另一个数组，对于每个元素 i，检查 x - i 是否在哈希集中。如果存在匹配，则 (i, x - i) 就是一个解。这一步需要线性时间。
Yes it's possible in linear time under these assumptions:
1) Convert one of the arrays into a hash set with approximately O(1) time complexity for lookups. Construction of the hash set takes approximately linear time.
2) Iterate over the other array and for each element i, check if x - i is in the hash set. If there is a match then (i, x - i) is a solution. This step requires linear time.
我想不出线性时间算法，但我可以想到一个 O (m log n) 解决方案，其中 m 是较大列表的长度，n 是较小列表的长度。
设 n 为较小列表的长度，m 为较大列表的长度。
步骤 1：对较小的列表进行排序（例如合并排序）：O(n log n)
步骤 2：对于较大列表中的每个项目，尝试在排序列表中查找（目标编号 - 项目）。
如果找到匹配项，则您已找到您要查找的两个号码。 O (m log n)。
复杂度为 O (n log n) + O (m log n)，即 O (m log n)，因为 m 是较大的列表。
I can not think of a linear time algorithm, but I can think of a O (m log n) solution where m is the length of the larger list and n is the length of the smaller list.
let n be the length of the smaller list and m be the length of the larger list.
Step 1: sort the smaller list (merge sort for example): O(n log n)
Step 2: for each item in the larger list, try to find (target number - item) in the sorted list.
If you find a match, you have found the two numbers you are looking for. O (m log n).
The complexity is O (n log n) + O (m log n) which is O (m log n) because m is the larger list.