LeetCode #1 Two Sum

題目

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

翻譯

這題有刷過題的人應該都會知道，就很像英文第一個單字就是 abandon。
給定一個陣列，找出兩數和為 Target，並且回傳這兩個數字的 index 陣列。

思維

需要給定一個陣列，並且將內部兩個數字相加會等於傳入的目標值。

最簡單的做法就是跑兩層 for 迴圈，兩兩相加，看看是否符合目標值，可是這樣的方法就是 O(N^2)，效率不是很好。

換另外一個思考方式，我們先將陣列轉換成 HashMap，先將值當作 Key， index 當作 Value，這樣的好處就是我們可以直接透過搜尋值的方式來找到 index，接著我們跑一層 for 迴圈，先用目標值扣除掉目前的值以後，再從 Map 找尋是否有相同的值，如果有找到就代表兩個值都找到了。

實作

fun twoSum(nums: IntArray, target: Int): IntArray {
    val m = HashMap<Int, Int>()
    val res = IntArray(2)
    nums.forEachIndexed { index, i ->
        m.put(i, index)
    }
    nums.forEachIndexed { index, _ ->
        val t = target - nums[index]
        if (m.containsKey(t) && m[t] != index) {
            res[0] = index
            res[1] = m[t] ?: 0
        }
    }
    res.sort()
    return res
}