[LeetCode] 01. Two Sum

(easy)

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

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

You can return the answer in any order.

 

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

 

1. Brute Force

- O(n^2)

class Solution {
    fun twoSum(nums: IntArray, target: Int): IntArray {
        nums.forEachIndexed { index, num ->  
            nums.forEachIndexed { index2, num2 -> 
                if (index != index2 && num + num2 == target) {
                    return intArrayOf(index, index2)
                }
            }
        }
        return intArrayOf()
    }
}

2. Index Map

- O(n)

- 각 요소의 index를 value로 갖는 hashMap으르 만들고, 초기 주어진 nums 배열을 순회하면서 diff(target-num)값의 인덱스를 찾는다.

- 처음에 찾지못해도 뒤 요소의 diff 인덱스를 찾으면서 체크가 되기 때문에 loop를 한번만 돌면서도 값을 찾아낼 수 있다..

class Solution {
    fun twoSum(nums: IntArray, target: Int): IntArray {
        val hashMap = mutableMapOf<Int, Int>()

        nums.forEachIndexed { index, num ->  
            val diff = target - num
            val indexForDiffValue = hashMap[diff]

            indexForDiffValue?.let {
                return intArrayOf(indexForDiffValue, index)
            }
            hashMap[num] = index
        }
        return intArrayOf()
    }
}

 

나름 쉬운 문제이지만, 처음부터 hash map으로 풀생각을 못했다.

hash map을 다양한 용도로 활용하는 연습을 해야겠다.