[LeetCode/Swift] 1. Two Sum

 

💡 문제 (Easy)

Two Sum - LeetCode

 

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.

정수 배열 nums와 정수 target이 주어졌을 때, 이 두 숫자의 합이 목표값(target)이 되도록 하는 인덱스를 반환하세요.

각 입력이 정확히 하나의 해결책을 가지고 있다고 가정하며, 동일한 요소를 두 번 사용할 수 없습니다.

결과는 어떤 순서로든 반환할 수 있습니다.

 

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.

👩🏻‍💻 해결

1차 이중 for문 풀이

이 풀이는 간단하고 이해하기 쉽지만, 시간 복잡도 O(n^2)로 효율적이지 않다.

공간 복잡도 O(1)

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

 

2차 Dictionary 사용

이 풀이는 Dictionary를 사용하여 target과 nums의 각 요소 간의 차이를 추적한다.

1. 빈 딕셔너리를 초기화 (dict) : 이 딕셔너리에는 key(target - nums의 각 요소), value(nums 요소의 인덱스) 를 담을 예정 

2. nums 배열을 루핑하면서 enumerated() 메서드를 사용하여 nums의 각 요소(num)와 인덱스(index)를 접근한다.

3. 각 요소에 대해 targer - 요소(num) 값이 이미 딕셔너리(dict)에 있는지 확인.

 - true : 현재 요소(num) + 딕셔너리(dict)의 해당 인덱스(addent)의 요소 = target이 되므로 [딕셔너리의 값(addent), 인덱스(index)]를 반환하고 끝

 - false : 4번 실행 

4. target - 요소(num) 을 dictionary key로, 인덱스(index)를 value로 딕셔너리(dict)에 추가 -> 2번 계속 배열 루핑 실행

5. 2번 배열 루프가 완료되고 배열에서 두 요소의 합이 target이 되는 경우가 없음으로 판단하여 빈 배열 반환

시간 복잡도 O(n), 공간 복잡도 O(n) 으로 더욱 효율적으로 해결!

class Solution {
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
        var dict = [Int: Int]()

        for (index, num) in nums.enumerated() {
            if let addent = dict[num] {
                return [addent, index]
            } else {
                dict[target - num] = index
            }
        }
        return []
    }
}