java - 数组中的对数和

Question

我有一个整数数组，内容为[17, 1, 20, 4, 12, 9] 我想获取所有总和为 21 的对。例如在给定的数组输出中应该是这样的:

17,4
1,20
12,9

我可以使用两个循环实现相同的目的。但复杂度为 N^2。有没有什么有效的方法可以做到这一点。

Answer 1

这是一个使用 python 3.0+ 的解决方案。

您可以通过使用键对值数据结构(即字典)在 O(N) 中完成此操作。

方法:

1. 循环一次数组，检查当前元素减去 k 值的结果，即 (k-arr[i]) 是否存在于字典中，这意味着结果值k-arr[i]和当前元素arr[i]等于k。将这两个添加到字典中。

2. 如果字典中不存在k-arr[i]，则添加键 arr[i]，值为k-arr[i] .

3. 您还可以添加检查当前元素 arr[i] 是否大于 k。

    def getPair(arr, k, dict):
        for i in range(len(arr)):
            if k - arr[i] in dict.keys():
                pass
                #print(arr[i], " ", (k-arr[i]))
            else:
                if k > arr[i]:
                    dict[arr[i]] = (k-arr[i])
   
    arr = [17, 1, 20, 4, 12, 9, 23]
    dict = {}
    getPair(arr, 21, dict)
    print("result: " , dict)