Recca Chao 的 gitHub page

推廣網站開發,包含 Laravel 和 Kotlin 後端撰寫、自動化測試、讀書心得等。Taiwan Kotlin User Group 管理員。

View on GitHub

Kotlin Leetcode - 1. Two Sum

題目連接: https://leetcode.com/problems/two-sum/

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

解題思路

這題要加快的重點

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

來加快我們找到 atarget - 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 列表