给定两个大小相同的数组，从两个数组中找到两个元素，这些元素的总和具有最小的绝对值

Question

我昨天接到了这个问题的任务，从那时起就试图找到一个有效的解决方案。
解决方案的细节是：给定两个数组 a[n]， b[n]，找到一对 (a[i]，b[j](，使 abs(a[i]+b[j]( 尽可能小。这两个数组由不大于 10 亿的整数元素组成，这里的 n 最多为 10000。
我知道这里由两个 for 循环组成的解决方案是不切实际的，因为数组大小小于或等于 10000。
我正在考虑一个解决方案，我将以一种我还没有发现的方式对这些元素进行排序，以便我们可以轻松识别具有最小绝对值的总和，因为我的班级正在学习排序算法。
你能帮我弄清楚这里的方式吗？
PS：对不起，我不能在这里输入数学符号。

Answer 1

我有一个Python代码，可以在O(nlogn + mlogm) + O(m+n) = O(nlogn + mlogm)时间内解决问题，其中n是第一个数组的长度，m是第二个数组的长度。这是代码：

arr1.sort()
arr2.sort(reverse = True)
n = len(arr1)
m = len(arr2)
print arr1
print arr2
minim = abs(arr1[0] + arr2[0])
i = 0
j = 0
while i<n and j<m:
   minimum = abs(arr1[i] + arr2[j])
   minim = min(minim,minimum)
   if arr1[i]>0 and arr2[j]>0:
      j += 1
   elif arr1[i]<=0 and arr2[j]<=0:
      i += 1
   elif arr1[i]>0 and arr2[j]<=0:
      if abs(arr1[i]) > abs(arr2[j]):
          j += 1
      else:
          i += 1
   elif arr1[i]<=0 and arr2[j]>0:
      if abs(arr1[i]) > abs(arr2[j]):
          i += 1
      else:
          j += 1
print minim

例：

arr1[] = [-23, -10, 30, 44, 45]

arr2[] = [61, 55, 32, 22, -55]

答：1

Answer 2

您可以否定其中一个列表并将其与另一个列表一起排序。在此新列表中，您将查找距离最小的两个连续条目，并且这两个条目来自每个原始列表。

如果a[i], i=0,1,...,n是第一个，b[j], j=0,1,...,n是第二个，那么min(|a[k]+b[l]|)=min(|a[k]-(-b[l])|).因此，我们可以最小化某些k,l的a[k]和-b[l]之间的差异，而不是最小化某些k,l的a[k]和b[l]之和。所以我们寻找一对a[k]，-b[l]尽可能靠近。这样的对必须在通过i,j=0,1,...,n a[i], -b[j]排序获得的列表中是连续的，c[t]长度为2n。

排序c是 O(n log n(，贯穿c是 O(n(，因此运行时间以排序为主。