[LeetCode] Two Sum

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

문제

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 <= 10⁴
- 10⁹ <= nums[i] <= 10⁹
- 10⁹ <= target <= 10⁹
- Only one valid answer exists.

고민

주어진 integer 배열에서 두개의 요소를 더해 target 이 될 수 있는 요소를 찾는 것이다.
하지만, 하나의 요소를 두번 사용할 수는 없고 target이 될 수 있는 요소가 존재한다고 가정해야한다.
요소를 어떤 순서로 반환해도 상관없다는 조건이 있다.

그렇다면, 모든 요소를 순회하며 찾아야할 것 같다.
기준은 가장 첫번째 요소(index = 0)로 시작하여 모두 순회해야할 것 같은데, 나로써는 2중 for문을 생각하였다.

해결

class Solution {
    fun twoSum(nums: IntArray, target: Int): IntArray {
        for (i in nums.indices) {
            for (j in i + 1 until nums.size) {
                if (nums[i] + nums[j] == target) {
                    return intArrayOf(i, j)
                }
            }
        }
        return nums
    }
}

첫번째 요소를 기준으로 그 이후부터 새로운 for 문으로 그 다음 요소들의 합을 확인하는 방식으로 했다.

결과

모든 테스트 케이스가 다 통과 되었지만, Runtime 시간은 29ms 로 좋은 코드는 아닌 것 같다.

후기

class Solution {
    fun twoSum(nums: IntArray, target: Int): IntArray {
        val hashMap = HashMap<Int,Int>()
        var start = 0
        var end = nums.size-1
        while(start <= end){
            val startDiff = target - nums[start]
            if(hashMap.containsKey(startDiff)){
                return intArrayOf(hashMap[startDiff]!!, start)
            }
            hashMap[nums[start]] = start
            val endDiff = target - nums[end]
            if (hashMap.containsKey(endDiff)) {
                return intArrayOf(hashMap[endDiff]!!, end)
            }
            hashMap[nums[end]] = end
            start++
            end--
        }
        return intArrayOf()
    }
}

0ms 가 소요된 코드를 확인해보니 target 을 만들기 위한 첫번째 숫자와 두번째 숫자를 각각 구해서 찾는 방식으로 보인다.
한번의 루프에서 왼쪽에서 가운데로, 오른쪽에서 가운데로 이동하며 점점 좁혀오며 찾는 방식인 것처럼 보인다.
조금 복잡해 보인다. 다른 코드를 좀 더 봐야겠다.

class Solution {
    fun twoSum(nums: IntArray, target: Int): IntArray {
        val map = hashMapOf<Int,Int>()
        for((index,num) in nums.withIndex()){
            val complement = target - num
            if(map.containsKey(complement)){
                return intArrayOf(map[complement]?:0,index)
            }
            map[num]=index
        }
        throw IllegalArgumentException("No hay indices")
    }
}

위의 코드와 비슷한 방식인 `HashMap` 과 선형 탐색 방식으로 진행했다.
하지만, 위의 코드보다는 더 짧고 확실해 보인다. (근데 왜 throw를 던지지..? 굳이..?)
나 나름대로 풀이를 해보자면, 결국 target 을 구하기 위해서는 특정 요소 2개가 더해져야하는것이기때문에 for문으로 순회를 하면서 target 에서 각 요소를 뺀 숫자를 구해서 찾는 방식으로 보인다.
해당 방법으로 다시 한번 Runtime 해봐야겠다.

class Solution {
    fun twoSum(nums: IntArray, target: Int): IntArray {
        val map = hashMapOf<Int,Int>()
        for((index,num) in nums.withIndex()){
            val complement = target - num
            if(map.containsKey(complement)){
                return intArrayOf(map[complement]?:0,index)
            }
            map[num]=index
        }
        return intArrayOf()
    }
}

(모방은 창조의 어머니🫣)
나는 throw를 던지지 않고 그냥 빈 숫자 배열을 반환했다. 많이 줄었다!!!!!

다음에 비슷한 문제가 나온다면, 잊지않고 한번 사용해보아야겠다.