两个排序数组,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")

我认为这是扭曲线性时间的双重循环,但你怎么会迭代2个列表呢？任何想法将不胜感激.

Answer 1

你可以做的是从一个列表中的最高点开始,而在另一个列表中从最低点开始,并检查总和.

如果总和是你的目标,你就完成了.

如果它太高,请转到第一个列表中的下一个最高值.

如果它太低,请转到第二个中的下一个最低值.

如果您在没有到达目标的情况下浏览两个列表,则返回false.