在给定总和的数组中定位两个元素

Question

如何在数组中找到这样的元素，使它们的总和等于给定的数字k.例如，有一个数组{1,2,4,1,1,5}和k=2，所以元素是{1,1}，{1,1，{1,1}。现在我在这里看到了一个问题，它为这个 https://stackoverflow.com/questions/4259515/given-an-unsorted-array-find-any-two-elements-in-the-array-whose-sum-is-equal-t 提供了解决方案。

现在我很想知道是否有任何方法可以找到这些元素的位置，即它们在数组中的位置。我所说的位置是指它们在数组中的索引号。如果我使用排序，那么数组的位置会发生变化，所以我想我不能使用它。是否有任何最佳算法来查找位置。如果我使用散列并且给定的数组有重复项，那么就会出现问题。

Answer 1

一种方法是有一个Dictionary<int, List<int>>并用项目及其索引填充它。示例{1, (0,3,4)},{2,(1)}，然后检查数组中的每个内容，并查看字典中是否有K-item，其中包含比项目different index。顺便说一句，您可以在遍历数组的同时执行此操作，因此运行时O(n).

Answer 2

它平均可以用 O（n+m） 完成，使用哈希映射。（n是数组的大小，m是输出的大小）。
只需在遍历时存储每个元素及其索引即可。一旦你找到一个元素，它的k补码已经在映射中 - 打印两个索引（一个来自迭代，一个是来自映射的值）。

伪代码（使用多映射语义 - 每个元素可以附加多个值）：

map <- empty hash map
for each e in array at index i:
    if e is in map:
        print i, map.get(e) //current index and already stored indices
    map.add(k-e,i) //add the element to the hash map