[Leetcode] 1. Two Sum 해시맵 풀이 해석 (Swift 풀이)

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

Two Sum 문제의 해시를 이용한 대표적인 풀이는 다음과 같다

# Python 풀이
class Solution(object): 
    def twoSum(self, nums, target): 
        complement_index = {} 
        for i in range(len(nums)): 
            if nums[i] in complement_index: 
                return [complement_index[nums[i]], i] 
            else: 
                complement_index[target - nums[i]] = i

complement_index가 바로 해시맵, 즉 딕셔너리이다.

if nums[i] in complement_index: 이 부분은 단 한번만 실행이 된다. 답을 찾았을 경우.

그렇다면

else: 부분이 중요해 보이는데,

else에서는 (num[i]와 더해서 target이 되는) 수의 인덱스를 해시맵에 저장해주고 있다

즉 complement_index에 저장되있는 key, value의 쌍은,

key + nums[value] = target의 관계를 가진다.

다시말해서 key와 더해서 target이 되는 수의 인덱스가 value에 저장되어있다.

따라서 nums[i] 가 complement_index 안에 있다면(if nums[i] in complement_index)

nums[i]와 더해서 target이 되는 수가 있다는 것이고 그 인덱스가 complement_index[nums[i]]이다

따라서 return [complement_index[nums[i]], i]을 하면 된다.

// Swift 풀이
class Solution {
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
        var compleIdx: [Int: Int] = [:]
        
        for i in 0..<nums.count {
            if let compleIdx = compleIdx[nums[i]] {
                return [compleIdx, i]
            } else {
                compleIdx[target-nums[i]] = i
            }
        }
        
        return []
    }
}