Daily LeetCode Challenge - 1. Two Sum

Problem From.
https://leetcode.com/problems/two-sum/

오늘 문제는 주어진 배열에서 각각 다른 인덱스에 있는 두 수를 더해서 target 을 만들 수 있을때, 각각의 인덱스를 array 에 담아서 return 하는 문제였다.

배열에서 하나를 잡고 나머지 하나를 선택한 뒤 target 이 되는지 확인하는 작업은 O(N^2) 의 시간이 걸리므로, 비효율적이다.

더 빠른 O(N) 의 시간에 문제를 해결하기 위해서, map 을 사용하여, 배열을 처음부터 끝까지 한번만 탐색하도록 할 수 있다. 먼저 한 원소를 볼때, target - 해당원소 가 map 에 있으면 map 에 저장되어있는 index 와 현재 index 를 반환하면 되고, 없으면 map 에 현재 인덱스를 저장해주는 식으로 하면, 배열을 처음부터 끝까지 한번만 탐색하면서 문제를 해결할 수 있다.

class Solution {
    fun twoSum(nums: IntArray, target: Int): IntArray {
        
        val map = hashMapOf<Int, Int>()
        for(i in 0 until nums.size) {
            
            if(map.contains(nums[i])) {
                return intArrayOf(map[nums[i]]!!, i)
            }else {
                map.put(target - nums[i], i)
            }
            
        }
        
        return intArrayOf(-1, -1)
    }
}