Нахождение пары значений, которые складываются в данную сумму

Question

lst = [3, 4, 1, 2, 9]

givenSum = 12
table = {}
x = 0
y = 0

for i in range(0, len(lst)):
    table[givenSum - lst[i]] = 1
    i += 1

for x in table:
    for y in table:
        if (x + y) == givenSum:
            print(x, "and", y, "is equal to", givenSum)
            break

Это вывод

9 and 3 is equal to 12
3 and 9 is equal to 12

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

Answer 1

Существуют более эффективные решения, но для устранения проблемы внесите минимальные изменения в код:

lst = [3, 4, 1, 2, 9]
givenSum = 12

for x in range(0, len(lst) - 1):
    for y in range(x + 1, len(lst)):
        if lst[x] + lst[y] == givenSum:
            print(lst[x], "and", lst[y], "is equal to", givenSum)
            break

Это выведет

3 and 9 is equal to 12

Обратите внимание, что избыточный table полностью удалено из кода.

Если вы запустите его для лучшего теста:

lst = [3, 4, 5, 6, 7, 1, 2, 9]

будет напечатано

3 and 9 is equal to 12
5 and 7 is equal to 12

Answer 2

Во-первых, чтобы выяснить, почему цикл продолжается и дает второй выходной сигнал, break может выйти только из его непосредственного значения l oop. Поскольку у вас есть вложенный l oop, break только останавливает for y in table: внутренний l oop, но позволяет for x in table external l oop перейти к следующей итерации. Таким образом, в конечном итоге x сможет впоследствии принять значение 3, что даст вам два выхода, которые вы видите.

Итак, если вам нужен способ полностью остановить итерацию, когда решение найдено, вам нужно либо связать операторы break в цепочку, используя синтаксис for else (что, возможно, может будь жестким к прочтению) следующим образом:

for x in table:
    for y in table:
        if (x + y) == givenSum:
            print(x, "and", y, "is equal to", givenSum)
            break #breaks from inner loop
    else: #for else syntax: this block runs if and only if there was no break encountered during looping.
        continue #jumps the outer loop to next iteration
    break #this break is set at outer loop's level. Essentially, we can only reach this portion if there is a break in the inner loop.

For else говорит: прогони всю итерацию и, если разрыв не найден, выполняет код в блоке else. По сути, «else» для «for else» походит на «for - no break».

Однако, более простой альтернативой является использование функции с return (что также облегчает прочитайте код).

def find_given_sum(lst, givenSum):
    table = {}
    x = 0
    y = 0

    for i in range(0, len(lst)):
        table[givenSum - lst[i]] = 1
        i += 1

    for x in table:
        for y in table:
            if (x + y) == givenSum:
                print(x, "and", y, "is equal to", givenSum)
                return #this returns immediately out of the function, thus stopping the iteration.

Кроме того, вы могли бы просто повторить условие прерывания, но повторение кода, как правило, не является хорошей практикой.

Надеюсь, это поможет решить, почему два выхода печатается. Теперь, что касается самого решения, на самом деле есть гораздо лучший способ решить это. Он основан на идее комплиментов, которые вы, кажется, чувствуете в своей таблице. Но это не требует итерации по самой таблице. Как подсказка: идеальное решение работает в O(n) времени. Я не буду обсуждать идеальное решение, но надеюсь, что это побудит вас найти лучший подход.

Answer 3

Цикл дважды для n элементов стоит O (N ^ 2) времени, что неэффективно для больших списков. Изменен и протестирован код для использования ha sh map / dictionary для хранения элементов списка, и теперь это займет всего O (N) времени.

Map = dict()
lst = [3, 4, 1, 2, 9]
givenSum = 12

for i in range(0, len(lst)):
    rem=givenSum-lst[i]
    if rem in Map:
        print lst[i],lst[Map[rem]]
    else:
        Map[lst[i]]=i

1. Сохраните значение каждого элемента списка в карту всякий раз, когда она не существует в карте.
2. На каждой итерации, возьмите разность между GivenSum и текущим элементом на этой итерации, а затем найдите эту разницу в карте.
3. Если это существует, значит, пара существует или нет.

В этом подходе вы запускаете l oop только один раз, что занимает O (N) время, потому что доступ к элементам на карте ha sh равен O (1) / постоянному времени.

Answer 4

Используйте itertools для получения результата

import itertools
sum = 10
lst = [3, 4, 1, 2, 9]
ans = list(filter(lambda x : x[0]+x[1] == sum,itertools.combinations(lst, 2)))