时间戳

首页 > 解决方案 > 向 Python 字典添加重复键（“Two Sum”问题）

python - 向 Python 字典添加重复键（“Two Sum”问题）

问题描述

我一直在尝试将重复的键添加到我的 python 字典（表）中，以解决“两个 Sum”问题。

给定一个整数数组，返回两个数字的索引，使它们相加到一个特定的目标。

我现在已经意识到这是不可能的，并且会感谢任何关于如何在没有蛮力的情况下解决这个问题的想法或建议。请记住，我这周开始尝试学习 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}

标签： pythonpython-3.xdictionaryduplicates

解决方案

您根本不需要存储索引，因为两个和问题不关心数字的位置，只关心找到它们。这可以通过以下方式实现：

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以存储出现特定值的索引列表，这将解决该问题。

推荐阅读