sumOfTwo Превышение срока действия CodeFights Практика собеседования

Question

Я пытаюсь выполнить sumOFTwo на CodeFights.com, но я, к сожалению, не могу его завершить, чтобы просмотреть решение. Все мои тесты продолжались до 15-го скрытого теста, и он говорит, что он превышает срок.

Задача - у вас есть два целых массива a и b и целочисленное целевое значение v. Определите, существует ли пара чисел, где одно число берется из a и другого из b, что может быть добавляется вместе, чтобы получить сумму v. Возвращаем true, если такая пара существует, в противном случае возвращает false.

Мой код -

def sumOfTwo(a,b,v): 
    a.sort() 
    b.sort() 

    if(0 in a and v in b): 
     return True 
    elif(v in a and 0 in b): 
     return True 
    else: 
     for i in a: 
      for j in b: 
       if(i + j == v): 
        return True 
    return False 

Я знаю, что это может быть сморщенные примерно до 6 строк кода, но я продолжал добавлять в строках, которые могли бы помочь код возможно закончить быстрее. Есть ли какие-то другие оптимизации, которых я не вижу.

Answer 1

Вы можете просто включить один из списков set, перебирать в другой список и посмотреть, если v - value_from_list существует в set:

def sumOfTwo(a,b,v): 
    b = set(b) 

    return any(v - x in b for x in a) 

print(sumOfTwo([3, 6, 7], [2, 1], 9)) 
print(sumOfTwo([3, 6, 7], [2, 1], 10)) 
print(sumOfTwo([3, 6, 7], [2, 1], 4)) 
print(sumOfTwo([3, 6, 7], [2, 1], 3)) 

Выход:

True 
False 
True 
False 

Временная сложность выше O (n).

Answer 2

Это то, что у меня есть. Он проходит все тесты, скрытые в комплекте, но он занимает слишком много времени на четырех скрытых тестах.

def sumOfTwo(a, b, v): 
    for i in a: 
    if((v-i) in b): 
     return True 
    return False 

@ Ответ niemmi проходит часть времени. Я не знал, что наборы быстрее, чем массивы/списки. Спасибо, приятно знать. Если я добавлю b=set(b) до цикла for, он пройдет.