两个排序数组，2个元素的总和等于一定数量

I was wondering if I could get some help. I want to find an algorithm that is THETA(n) or linear time for determining whether 2 numbers in a 2 sorted arrays add up to a certain number.

我想知道我是否能得到一些帮助。我想找到一个THETA（n）或线性时间的算法，用于确定2个排序数组中的2个数是否加起来一定数。

For instance, let's say we have 2 sorted arrays: X and Y

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

I want to determine if there's an element of X and an element of Y that add up to exactly a certain number, let's say 50.

我想确定是否有一个X元素和一个Y元素加起来恰好是一个特定的数字，让我们说50。

I have been able to come up with these algorithms in Python so far, but I am pretty sure they are order of THETA(n^2) rather than THETA(n).

到目前为止，我已经能够在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")

I'm thinking it's the double for loops that break the linear time, but how else would you iterate through 2 lists? Any thoughts would be appreciated.

我认为这是打破线性时间的双循环，但你怎么会迭代2个列表呢？任何想法将不胜感激。

2 个解决方案

#1

What you can do is start with the highest in one list and the lowest in the other, and check the sum.

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

If the sum is your target, you're done.

如果总和是你的目标，你就完成了。

If it's too high, go to the next highest value in the first list.

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

If it's too low, go to the next lowest value in the second.

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

If you go through both lists without reaching the target, you return false.

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

#2

Here is a 2n for you which doesn't even need sorting:

这是一个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)

#1