将重复键添加到 Python 字典("Two Sum"问题)

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

不太确定您具体需要 dup 键做什么，但您可以使用值列表：

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

我相信这项任务有更好的解决方案，很高兴看到其他答案。

Answer 3

我不明白为什么你需要一个字典，除非你有多个目标。 我会改用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 4

我会对数组进行排序，执行某种二叉搜索来搜索目标的索引(或直接次要索引(，并在索引中查找较小索引和使用二叉搜索找到的索引之间的"两个和"。

例如： 数组 = [5,1,8,13,2,4,10,22] 目标 = 6

sorted_array = [1,2,4,5,8,10,13,22] binary_search_index = 4(数字 5(

所以知道你把你的数组缩小到：[1,2,4,5]，你可以在那里查看 de "两个总和"，可能使用 de min 和 max 索引。