Kotlin Leetcode - 1. Two Sum

題目連接

class Solution {
    fun twoSum(nums: IntArray, target: Int): IntArray {
    }
}

解題思路

這題要加快的重點

是想到利用 hashMap 搜尋比較快（log(n)）的特點

來加快我們找到 a 和 target - a 的時間

---

建立一個 hashMap

當我們讀取 nums[i] 時

在這個 hashMap 裏面搜尋是否存在 target - nums[i]

如果沒有的話，將 nums[i] 放入 hashMap 並繼續往下

這樣的話，只需要從頭到尾遍歷一次陣列

即可找到答案

Kotlin 參考解答

點擊展開解答

class Solution {
    fun twoSum(nums: IntArray, target: Int): IntArray {
        val map = hashMapOf<Int, Int>()
        for (i in nums.indices) {
            if (map.containsKey(target - nums[i])) {
                val tmp = map[target - nums[i]]!!.toInt()
                return intArrayOf(tmp, i)
            }
            map[nums[i]] = i
        }
        throw IllegalArgumentException("No two sum solution")
    }
}

其中 for 的部分可以改寫成 forEachIndexed

class Solution {
    fun twoSum(nums: IntArray, target: Int): IntArray {
        val map = hashMapOf<Int, Int>()
        nums.forEachIndexed { i, _ ->
            if (map.containsKey(target - nums[i])) {
                val tmp = map[target - nums[i]]!!.toInt()
                return intArrayOf(tmp, i)
            }
            map[nums[i]] = i
        }
        throw IllegalArgumentException("No two sum solution")
    }
}

---

• 回到 leetcode 列表
• 回到 Grind 75 列表