Вопрос:
Эту проблему недавно задал Google.
Учитывая список чисел и число k, вернуть любые два числа из списка в сумме k.
Например, учитывая [10, 15, 3, 7] и k из 17, вернуть true, поскольку 10 + 7 равно 17.
Бонус: сможете ли вы сделать это за один проход?
Решение [pyth3.8]:
def find2sum(arr,key):
```для i в диапазоне (len(arr)):
``````для j в диапазоне (i,len(arr)):< br /> ``````````if a[i]+a[j]==key:
````````````` возвращает True
```вернуть False
a = list(map(int,input().split()))
k = eval(input())
печать (найти2сумму (а, к))
Это требует временной сложности O (n²).
def find2sum(arr,key):
```arr.sort()
```для i,j в zip([k для k в диапазоне(len(arr))],[x для x в диапазоне (len(arr)-1,-1,-1)]):
``````sumo = arr[i]+arr[j]
```` ``if sumo‹key:
`````````i+=1
``````elif sumo›key:
```````` `j-=1
``````else:
`````````возвратить True
```вернуть False
a = list(map(int,input().split()))
k = eval(input())
печать (найти2сумму (а, к))
Это требует временной сложности O (n).
Доказательство по индукции. Пусть a[0,n] — массив длины n+1 и p = (p1, p2), где p1, p2 — целые числа, а p1 <= p2 (w.l.o.g.). Предположим, что a[0,n] содержит p1 и p2. В случае, если это не так, алгоритм, очевидно, верен.
