Logic behind Two Number Sum Algorithm-CodePudding

Could someone explain to me the logic behind this hashMap algorithm? I'm getting confused about how the algorithm receives the total sum. I'm starting to learn about algorithms, so it's a little confusing for me. I made comments in my code to pinpoint each line code, but I'm not sure I'm grasping logic correctly. I'm just looking for an easier way to understand how the algorithm works to avoid confusing myself.

//**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*

CodePudding user response：

Sure, I can walk you through it. So we have a list of numbers, are we are trying to find two numbers that add together to make the specified target. To do this, for each number x, we check if (target - x) is in the list. If it is not, then we add x to the list. If it is, then we return x and (target - x).

Step 4 in your code is the part where we check if (target - x) is in the list. To see why this makes sense, let's walk through an example.

Say we have [2, 3, -1] and our target is 1. In this case, we first consider x = 2 and check our hashmap for (target - x) = (1 - 2) = -1. Since -1 is not in the hashmap, we add 2 to the hashmap. We then consider x = 3 and check for (1 - 3) = -2. Again, -2 is not in the hashmap, so we add it. Now we check x - -1. In this case, when we check (target - x) = (1 - (-1)) = 2, 2 is in the hashmap. Intuitively, we have already "seen" 2, and know that 2 and -1 can be added to get our value.

This is what provides the speed optimization over checking every two numbers in the list.