给定两组“n”数 A 和 B。从 A 中选择一个元素，从 B 中选择一个元素，使得总和等于给定值“val”。
我的解决方案如下：
我们可以对集合 A 和集合 B 的元素进行散列，并检查集合 A 中的每个元素是否 val-arr[i] 存在于集合 B 的散列中。这将花费 O(n) 时间和 O(n) 空间 有没有更好的解决方案，空间为 O(1)，时间为 O(n)？
问问题
2926 次
1 回答
1
由于您的两个数组都未排序，因此您别无选择，只能逐个查看每个元素。因此，您不能低于O(n)运行时间。我认为您使用的方法还可以。
阅读这些相关帖子：
给定两个数组 a 和 b。找到所有元素对 (a1,b1)，使得 a1 属于数组 A，b1 属于数组 B，其和 a1+b1 = k
于 2012-04-07T17:04:20.970 回答