Two Sum

1. Two Sum

Problem Statement:

Given an array of integers and a target value, find two numbers in the array whose sum is equal to the target. Return the indices of those two numbers.

Input Example:

nums = [2, 7, 11, 15, 6, 3, 5, 4, 0, 9]
target = 9

Output Example:

[0,1]
[4,5]
[6,7]
[8,9]

Explanation:

nums[0] + nums[1] = 2 + 7 = 9

Solution:

If we use multiple loop:

fun main() {
    val arr = arrayOf(2, 7, 11, 15, 6, 3, 5, 4, 0, 9)
    val target = 9

    for (i in 0 until arr.size - 1) {
        for (j in i + 1 until arr.size) {
            if (arr[i] + arr[j] == target) {
                println("[$i,$j]")
            }
        }
    }
}

If restricted for using single loop

fun main() {
    val arr = arrayOf(2, 7, 11, 15, 6, 3, 5, 4, 0, 9)
    val target = 9

    val map = mutableMapOf<Int, Int>() // number -> index

    for (i in 0 until arr.size) {
        val currentNumber = arr[i]
        val requiredNumber = target - currentNumber

        if (map.containsKey(requiredNumber)) {
            val previousIndex = map[requiredNumber]
            val currentIndex = i

            println("[$previousIndex,$currentIndex]")
        }

        map[currentNumber] = i
    }
}