二数和算法背后的逻辑

Question

谁能给我解释一下这个hashMap算法背后的逻辑？我对算法如何接收总和感到困惑。我开始学习算法，所以这对我来说有点混乱。我在我的代码中做了评论以查明每一行代码，但我不确定我是否正确掌握了逻辑。我只是在寻找一种更简单的方法来理解算法的工作原理，以避免混淆自己。

//**calculate Two Number Sum
func twoNumberSum(_ array: [Int], _ targetSum: Int) -> [Int] {

    //1) initilize our Array to hold Integer Value: Boolean value to store value into hashTable
    var numbersHashMap = [Int:Bool]()
    //2) create placeHolder called number that iterates through our Array.

    for number in array {

    //3) variable = y - x 
        let match = targetSum - number 
        
       //4) ??
        if let exists = numbersHashMap[match], exists {

       //5)  match = y / number = x
        return [match, number] // 
    } else {
//6) Store number in HashTable and repeats 
          numbersHashMap[number] = true
        }
    }
    return []
    
}
 twoNumberSum([3,5,-4, 8, 11, 1, -1, -6], 10)

// x = Number
// y = Unknown *Solve for Y*

Answer 1

当然，我可以引导您完成它。所以我们有一个数字列表，我们是否正在尝试找到两个加在一起以构成指定目标的数字。为此，对于每个数字 x，我们检查 (target - x) 是否在列表中。如果不是，则我们将 x 添加到列表中。如果是，那么我们 return x 和 (target - x).

您代码中的第 4 步是我们检查 (target - x) 是否在列表中的部分。要了解为什么这是有道理的，让我们来看一个例子。

假设我们有 [2, 3, -1] 并且我们的目标是 1。在这种情况下，我们首先考虑 x = 2 并检查我们的散列映射 (target - x) = (1 - 2) = - 1.由于 -1 不在哈希图中，我们将 2 添加到哈希图中。然后我们考虑 x = 3 并检查 (1 - 3) = -2。同样，-2 不在 hashmap 中，所以我们添加它。现在我们检查 x - -1。在这种情况下，当我们检查 (target - x) = (1 - (-1)) = 2 时，2 在 hashmap 中。直觉上，我们已经“看到”了2，知道2和-1可以相加得到我们的值。

这就是在检查列表中的每两个数字时提供速度优化的原因。

二数和算法背后的逻辑

Logic behind Two Number Sum Algorithm

swift

algorithm

data-structures

hashtable