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

Question

我一直在尝试向我的 python 字典（表）添加重复键以解决“二和”问题。给定一个整数数组，返回两个数字的索引，使它们相加为特定目标。我现在意识到这是不可能做到的，并且会很感激关于如何在没有蛮力的情况下解决这个问题的任何想法或建议。请记住，我这周开始尝试学习 Python。所以我很抱歉有一个简单的解决方案numbers = [0, 0, 0, 0, 0, 0, 0]  # initial listtarget = 6  # The sum of two numbers within list# Make list into dictionary where the given values are used as keys and actual values are indicestable = {valueKey: index for index, valueKey in enumerate(numbers)}print(table)>>> {0: 6}

Answer 1

我不明白为什么你需要一个字典，除非你有多个目标。我会用 aset代替。

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 2

我会对数组进行排序，进行某种二进制搜索来搜索目标的索引（或直接次要索引），并在较小的索引和使用二进制搜索找到的索引之间的索引中查找“二和”。

例如：数组 = [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 min 和 max 索引。