java - 了解 Pair of Sum 和 codaddict 的算法

Question

我指的是以下question这是之前问过的。而且，我对那里提到的以下解决方案感兴趣:

我试图理解以下整数数组，但在迭代 #5 后我迷失了，如下所示:

假设我们的整数数组是:{1,2,3,4,8,9,10}，我们应该打印总和等于 12 的那些对。所以，我尝试了逐步分析如果我们应用上述方法会发生什么:

                             Key             Value   
Iteration 1 : i = 0       (12-1) = 11          1 
Iteration 2 : i = 1       (12-2) = 10          2
Iteration 3 : i = 2       (12-3) = 09          3
Iteration 4 : i = 3       (12-4) = 08          4
Iteration 5 : i = 4       // pairs.containsKey is true here so printing 
                             input[i] = 8   

谁能解释一下为什么我们要打印 input[i] = 08 和 pairs.get(input[i])) (迭代中也是 08 #) 5以上？

其次，就 codaddict 的算法而言，我在网上没有找到任何内容。

Answer 1

简单浏览了一下您引用的答案。回答你的问题，

why are we printing input[i] = 08 and pairs.get(input[i])) which is also 08 in iteration #5 above?

它正在打印input[i]，即8，以及pairs.get(input[i])，这意味着 pairs.get(8) 是 4。

---

您需要知道的是，那段 Java 代码没有实现 Codaddict 的逻辑。它看起来有点像，但它只是做了一些不同的事情:Codaddict 将输入值存储为键，将索引存储为值，而 Java 实现将 (sum-value) 存储为键和 值作为值。

Java 实现并不理智。它所做的事情可以简化为:

public static void printSumPairs(int []input, int sum){
    Set<Integer> previousInts = new HashSet<>();

    for (int i : input) {
        if (previousInts.contains(sum - i)) {
             System.out.print("" + (sum - i) + ", " + i);
        } else {
             previousInts.add(i);
        }
    }
}

这基本上实现了与 Java impl 相同的结果，并且(我相信)更容易理解。

不过，对于重复的数字不能很好地工作(这与原始的 Java impl 相同)。然而，拥有一个处理数字重复的逻辑实际上很容易。