两个排序数组，两个元素之和等于一定数目

问题描述

我想知道是否能得到一些帮助.我想找到一种THETA(n)或线性时间的算法，用于确定2个排序数组中的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.

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

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

我想确定是否有一个X元素和一个Y元素加起来等于一个特定的数字，比如50.

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.

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

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).

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")

我想这是打破线性时间的double for循环，但是您还会如何遍历2个列表?任何想法都将不胜感激.

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.

推荐答案

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

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.

如果您遍历两个列表而未达到目标，则返回false.

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

这篇关于两个排序数组，两个元素之和等于一定数目的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！