python - 两个排序数组，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

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

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

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

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

如果您通过两个列表都没有到达目标，则返回 false。