LeetCod - Two Sum

Difficulty

easy
https://leetcode.com/problems/two-sum/description/

Problem

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.

Example 1:

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

Input: nums = [3,2,4], target = 6
Output: [1,2]
Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

Constraints

• 2 <= nums.length <= 104

• -109 <= nums[i] <= 109

• -109 <= target <= 109

• Only one valid answer exists.

  
  
  

Solution

이 문제를 O(n)으로 어떻게 풀지 고민이 먼저 됐다. 다행히 문제에서는 target 값이 나오는데 무조건적인 답이 있는 케이스고 이를 시간복잡도만 고려해서 짜면 됐다.
그래서 map을 이용해서 단순하게 풀었지만 21ms가 나왔다

 fun twoSum(nums: IntArray, target: Int): IntArray {
        val map = hashMapOf<Int, Int>()
        nums.forEachIndexed { index, i ->
            map[i] = index
        }
        nums.forEachIndexed { index, num ->
            val result = map[target - num]
            if (result != null && result != index) {
                return intArrayOf(index, result).sortedArray()
            }
        }
        return intArrayOf()
    }

2ms로 푼 다른 풀이를 보니까 굳이 map에 값을 할당하지 않고 풀기도 한다.
그냥 return 하지말고 throw하는것도 방법일 듯 하다.

class Solution {
    fun twoSum(nums: IntArray, target: Int): IntArray {
        val numToIndex = HashMap<Int, Int>(nums.size) // 초기 용량 설정으로 리사이징 방지

        for (i in nums.indices) {
            val complement = target - nums[i]
            if (numToIndex.containsKey(complement)) {
                return intArrayOf(numToIndex[complement]!!, i)
            }
            numToIndex[nums[i]] = i
        }
        throw IllegalArgumentException("No solution found")
    }
}