arrays - 给定两个未排序的数组 A 和 B ，通过仅对其中一个数组进行排序，找到和(或差)等于给定 k 的一对元素

Question

假设我们有两个给定的未排序数组 A 和 B，找到一对元素(例如第一个元素属于 A，第二个元素属于 B)，它们的和(或差？)相等给定 k - 通过仅对其中一个数组排序。

我想知道是否有一种算法使用良好的复杂性。无论如何，我已经尝试使用该链接 Given two arrays a and b .Find all pairs of elements (a1,b1) such that a1 belongs to Array A and b1 belongs to Array B whose sum a1+b1 = k ，但我发现它没有帮助，因为我不喜欢那里提到仅使用一种排序的可能解决方案。

Answer 1

我的解决方案，假设问题没有空间限制，假设A有长度 n和 B有长度 k :

-对于每个元素a在数组中 A ( n 次迭代)，存储 k-a , -k-a和 k+a在具有 O(1) contains() 的 HashSet/一些类似数据结构中功能。

-然后，对于每个元素b在数组中 B ( k 次迭代)，检查是否 b在哈希集/ map 中使用 O(1) contains()功能。如果是，我们就完成并返回 b和相应的a值使得 a+b=k , a-b=k或 b-a=k (我不确定你是否想考虑这个问题的差异，这取决于你)。

总而言之，该算法的运行时间最长为 O(n+k)，空间复杂度为 O(3n)(假设 WLOG 为 n < k 以最大化效率)。这两项都是线性的，这意味着如果一对 (a,b)存在满足问题，会比较快的找到，不需要排序。

希望这会有所帮助，对于糟糕的格式感到抱歉(我希望 SO 支持 Latex，这对于解决此类问题会很好)。如果您需要帮助理解我所做的事情，请留下评论/问题，因为它可能不太清楚。