python - 使用字典在列表中查找加起来等于和的一对元素

Question

问题的背景:

在数组中查找具有给定总和的对。

给定一个未排序的整数列表，找到其中具有给定总和的一对。

示例:

列表 = [8, 7, 2, 5, 3, 1]

总和 = 10

输出 = 索引 0 和 2 (8, 2) 或 1 和 4 (7, 3)

这是我到目前为止所拥有的:

def find_pair_dict(ints: [int], sum_: int):

    dict_ = dict()

    # {
    #   element: index
    #   8: 0,
    #   7: 1,
    #   ...
    # }

    output = list()

    for i in range(len(ints)):
        diff = sum_ - ints[i]
        # print(diff)
        if diff not in dict_.keys():
            # int: index
            dict_[ints[i]] = i

        else:
            output.append((dict_[ints[i]], dict_[diff]))

    if not output:
        return "No pairs were found"
    return output

我使用 find_pair_dict([8, 7, 2, 5, 3, 1], 10) 调用此函数，但收到一个我不明白的错误。

错误

Traceback (most recent call last):
  File "find_pair_sum.py", line 62, in <module>
    print(find_pair_dict([8, 7, 2, 5, 3, 1], 10))
  File "find_pair_sum.py", line 53, in find_pair_dict
    output.append((dict_[ints[i]], dict_[diff]))
KeyError: 2

听起来2的元素不能添加？

Answer 1

几乎是一句台词:

def find_pairs(ints: [int], sum_: int):
    return {
        tuple(sorted((n, ints.index(sum_-i)))): (i, sum_-i) 
        for n, i in enumerate(ints) if sum_ - i in ints
    }


print(find_pairs([8, 7, 2, 5, 3, 1], 10))

结果:

{(0, 2): (2, 8), (1, 4): (3, 7), (3, 3): (5, 5)}

注意:字典的键是一个排序的元组。元组，因为列表不可散列并排序以避免两者 (0,2)和(2,0)显示为键(例如)。

解决方案中出现错误是因为第一次执行此行:

output.append((dict_[ints[i]], dict_[diff]))

如果 dict_ 的值是 {8: 0, 7: 1}和ints[i]是 2 。由于没有 2 的条目在字典中，您会收到此错误。