两个排序数组，2个元素的总和等于某个数

Question

我想知道是否可以得到一些帮助。我想找到一种算法，即 THETA(n) 或线性时间，用于确定 2 个排序数组中的 2 个数字是否加起来等于某个数字。

例如，假设我们有 2 个排序数组：X 和 Y

我想确定是否有 X 的一个元素和 Y 的一个元素相加正好等于某个数字，比方说 50。

到目前为止，我已经能够在 Python 中提出这些算法，但我很确定它们是 THETA(n^2) 的顺序而不是 THETA(n)。

def arrayTestOne(X,Y):
    S =[1 for x in X for y in Y if x+y == 50]

def arrayTestTwo(X,Y):
    for x in X:
        for y in Y:
            if x + y == 50:
                print("1")

我认为是双 for 循环打破了线性时间，但是您还能如何遍历 2 个列表？如有任何想法，我们将不胜感激。

Answer 1

这里有一个甚至不需要排序的 2n:

def check_array(x, y, needed_sum):
    y = set(y)
    return next(((i, needed_sum-i) for i in x if (needed_sum-i) in y), None)

Answer 2

你可以做的是从一个列表中最高的开始，另一个列表中的最低，然后检查总和。

如果总和是您的目标，那么您就完成了。

如果太高，转到第一个列表中的下一个最高值。

如果太低，则转到第二个下一个最低值。

如果您通过两个列表都没有达到目标，那么您 return 错误。

两个排序数组，2个元素的总和等于某个数

Two Sorted Arrays, sum of 2 elements equal a certain number

python

arrays

algorithm

big-o