Добавление дубликатов ключей в словарь Python (проблема «две суммы»)

Question

Я пытался добавить дубликаты ключей в свой словарь (таблицу) Python для решения проблемы «две суммы».

Учитывая массив целых чисел, вернуть индексы двухчисла такие, что они складываются в конкретную цель.

Теперь я понял, что это невозможно сделать, и буду признателен за любые идеи или предложения о том, как решить эту проблему без грубой силы.Пожалуйста, имейте в виду, что я начал пытаться изучать Python на этой неделе.Поэтому я прошу прощения за простое решение

numbers = [0, 0, 0, 0, 0, 0, 0]  # initial list
target = 6  # The sum of two numbers within list

# Make list into dictionary where the given values are used as keys and 
actual values are indices
table = {valueKey: index for index, valueKey in enumerate(numbers)}

print(table)

>>> {0: 6}

Answer 1

Вам не нужно хранить индекс вообще, потому что проблема двух сумм не связана с , где находится число, просто с их поиском.Это можно сделать следующим образом:

target = 6
numbers = [1, 5, 11, -5, 2, 4, 6, 7, 21]
hashTable = {}
results = []
for n in numbers:
    if ((target - n) in hashTable and hashTable[target - n] == None):
        hashTable[target - n] = n
    else:
        hashTable[n] = None

results = [[k, v] for k, v in hashTable.items() if v != None]
print(results)

В случае, если вы хотите, чтобы индекс ваших чисел, вы могли бы добавить второй словарь indices:

indices = {}
for i, n in enumerate(numbers):
    if ((target - n) in hashTable and hashTable[target - n] == None):
        hashTable[target - n] = n
    else:
        hashTable[n] = None
    indices[n] = i

results = [[indices[k], indices[v]] for k, v in hashTable.items() if v != None]
print(results)

Обратите внимание, что для обоихиз этих решений для работы, вы должны гарантировать, что каждый элемент появляется в списке только один раз.В противном случае ваши суммы были бы неоднозначными.Вы можете изменить indices для хранения списка индексов, в которых встречается конкретное значение, и это решит эту проблему.

Answer 2

Я не понимаю, зачем вам нужен дикт, если у вас не было нескольких целей.Я бы использовал set вместо.

numbers = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
target = 9
answer = set()
for i, iNumber in enumerate(numbers):
    for j, jNumber in enumerate(numbers):
        if i == j:
            continue
        mySum = iNumber + jNumber
        if (mySum == target):
            answer.add((i,j))

Answer 3

Я бы отсортировал массив, сделал какой-то двоичный поиск, чтобы найти индекс вашей цели (или ближайшего младшего) и найти «две суммы» в индексе между меньшим и индексом, найденным с помощью бинарного поиска.

Например: массив = [5,1,8,13,2,4,10,22] target = 6

sorted_array = [1,2,4,5,8,10,13,22] binary_search_index = 4 (число 5)

Итак, знайте, что вы сократили свой массив до: [1,2,4,5], и вы можете посмотреть там «две суммы», вероятно, используя de min имаксимальный индекс.

Answer 4

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

import collections

table = collections.defaultdict(list)

for i, value in enumerate(numbers):
    table[value].append(i)

diffs = enumerate(target - number for number in numbers)

for i, diff in diffs:
    if diff in table:
        indices = table[diff]
        indices.remove(i)
        if indices:
            print i, indices

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