理解和与密码成瘾算法对

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]))，这也是上面迭代#5中的08？

其次，我没有在网上找到任何关于密码成瘾算法的信息。

Answer 1

看了一下你引用的答案。为了回答你的问题，

为什么我们要打印inputi = 08和pairs.get(Inputi)，这在上面的迭代5中也是08？

打印input[i]是8，pairs.get(input[i])是pairs.get(8)是4。

您需要知道的是，这段Java代码并没有实现Cod瘾的逻辑。它看起来有点相似，但它只是在做一些不同的事情:Cod瘾将输入值存储为键，索引存储为值，而(sum-value)实现将value存储为键，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所推动的结果相同的结果，而且(我相信)更容易理解。

但是，重复的数字不能很好地工作(对于原始的Java impl来说是一样的)。然而，拥有一个处理数字重复的逻辑实际上是很容易的。

Answer 2

当i==4，input[i] == 8，但是pairs.get(input[i]))是pairs.get(8)，它等于4，因为在上一次迭代中，当我3岁时，我们执行pairs.put(k-input[i],input[i])，或者按单词pairs.put(12-4,4)顺序排列。

Answer 3

我认为您需要了解first.We的算法，想要在数组中找到数字对，其中和是K。

如果数组中有两个数字(x，y)，其中和是K，那么

x+y = k,
or y = k-x. 

对于一个数字x，我们将x映射到key (K)。

那么对于另一个数字y，如果我们能在地图中找到y，这意味着，有一个数字x被映射为(k-x)，等于y。现在我们可以从地图中找到原始的x并打印它。