Два сортированных массива, сумма из 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.

Answer 2

Вот 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)