从不同的数组中查找两个变量以获得特定复杂度的特定总和

Question

我是一名计算机科学专业的学生，这是我的第一年！所以，我认为这必须非常简单，但有些我就是无法理解。

所以-自己锻炼吧：

Def 得到两个包含实数 (int) 和一些 S (int) 的数组。需要找到 X（数组 1 中的一些整数）+ Y（数组 2 中的整数）= S。但是 - 复杂度必须为 O(n+m)，其中 n 和 m 是数组的长度。

def finding_sum(arr1, arr2, s):
  for i in arr1:
    if (s-i in arr2):
      return i, s-i

我考虑过 - 但 IN 模块就像遍历整个数组，这是 O(n*m)。

Answer 1

您可以创建一个辅助数据结构：

def finding_sum(arr1, arr2, s):
    lookup = {s-n for n in arr1}
    for n in arr2:
        if n in lookup:
            return s-n, n

集 lookup 需要线性时间来创建并提供 O(1) 包含检查。您可以使用 next:

来缩短它

def finding_sum(arr1, arr2, s):
    lookup = {s-n for n in arr1}
    return next((s-n, n) for n in arr2 if n in lookup)

你甚至可以使用 set intersection 来获得单线，但放弃任何短路：

def finding_sum(arr1, arr2, s):
    return next((s-n, n) for n in set(arr2).intersection(map(s.__sub__, arr1)))

Answer 2

将第二个列表转换为集合。转换是O(m)，集合查找是O(1)。

def finding_sum(arr1, arr2, s):
    set2 = set(arr2)
    for i in arr1:
        if s-i in set2:
            return i, s-i

Finding two variables from different arrays to get a specific sum in specific complexity