python - 找到加到某个值的数字对？

Question

我有一个 match 函数，它接受一个数字列表和一个目标数字，我想编写一个函数，在数组中找到两个数字相加到该目标。

这是我的方法:

>>> def match(values, target=3):
...     for i in values:
...             for j in values:
...                     if j != i:
...                             if i + j == target:
...                                     return print(f'{i} and {j}')
...                             return print('no matching pair')

这个解决方案是否有效？可以改进吗？

Answer 1

最好的方法将产生 O(NlogN) 的解决方案。

1. 你对列表进行排序，这将花费你 O(NlogN)
2. 列表排序后，您将获得两个索引，前者指向第一个元素，后者指向最新元素，您检查元素的总和是否与您的目标匹配。如果总和高于目标，则将上部索引向下移动，如果总和低于目标，则将下部索引向上移动。当上索引等于下索引时结束。该操作是线性的，可以在 O(N) 时间内完成。

总而言之，排序的复杂度为 O(NlogN)，索引的复杂度为 O(N)，整个解决方案的复杂度为 O(NlogN)。