[Swift] LeetCode: Two Sum

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

Two Sum - LeetCode

 

내가 작성한 코드

: 직관적..

class Solution {
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
        var result: [Int] = []
        
        for firstIndex in 0..<nums.count {
            for secondIndex in (firstIndex + 1)..<nums.count {
                if nums[firstIndex] + nums[secondIndex] == target {
                    result.append(firstIndex)
                    result.append(secondIndex)
                    return result
                }
            }
        }  
        return result
    }
}

 

 

다른사람의 코드를 보고 배워보자

// NOTE: Functional way

func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
	let map = nums.enumerated().reduce(into: [:]) { (result, this: (index: Int, value: Int)) in
		result[this.value] = this.index
	}
	var result = [Int]()
	nums.enumerated().forEach { (i, value) in
		if let j = map[target - value], i != j {
		 result = [i, j]
		}
	}
	return result
}

// NOTE: The smartest way

func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
	var map = [Int: Int]()
	for (i, n) in nums.enumerated() {
		let diff = target - n
		if let j = map[diff] {
			return [i, j]
		}
		map[n] = i
	}
	return []
}

 

와 정말 사람들은 똑똑하다..

 

아래의 함수의 방법으로 풀어보면

 

1. enumerated()  함수로 인덱스와 배열의 값을 가져와서 차례대로 for문을 돈다.

2. 현재 값에서 target에 대한 보수값을 구한다. 

3. 이 보수 값이 map dictionary에 있다면 (= 이미 앞에 나온 값이라면) 인덱스 값을 리턴해주고

4. 이 보수 값이 없다면 map dictionary에 이런 값이 있다고 저장해둔다.

 

 

4번에서 보수 값이 없을 때 값을 저장하는 방식은 

모든 값을 dictionary에 미리 저장해두는 것보다 시간복잡도 상으로 이득이다.

 

마지막 코드로 짜면 O(N) 시간에 코드를 풀 수 있다.