[ LeetCode ] 1 Two Sum

Link | LeetCode 1번 문제 : Two Sum

📌 About

일반적인 반복문 문제로 이중 반복 문을 통해 해결할 수 있다.

for (i in nums.indices)
    for (j in nums.indices)
        if (i != j && nums[i] + nums[j] == target) return intArrayOf(i, j)
return intArrayOf()

하지만 이러면 $O(N^2)$의 시간 복잡도를 가진다. $O(N)$으로 해결할 수 있어야 한다.

이는 Map을 사용하여 구현이 가능하다. Map<값, 인덱스>은 초기에 값이 없다.

num에 대해 target-num을 가지고 있으면 현재 index와 target - num의 index를 반환한다.

그렇지 않다면 map.put(num, idx)를 한다.

📌 Solution

Step 1. 비어 있는 map을 선언한다.

val map = mutableMapOf<Int, Int>()

Step 2. nums를 순차적으로 탐색한다.

nums.forEach { ... }

Step 3. target - num을 key 값으로 가지고 있으면 인덱스 배열을 반환한다.

if (map.containsKey(target - nums[it])) return intArrayOf(it, map[target - nums[it]]!!)

Step 4. key 값이 없으면 map에 현재 값을 추가한다.

map[nums[it]] = it

📌 Code

GitHub Repository

Kotlin

fun twoSum(nums: IntArray, target: Int): IntArray {
    val map = mutableMapOf<Int, Int>()
    nums.indices.forEach {
        if (map.containsKey(target - nums[it])) return intArrayOf(it, map[target - nums[it]]!!)
        map[nums[it]] = it
    }
    return intArrayOf()
}