[리트코드] 1. Two Sum

문제

https://leetcode.com/problems/two-sum/?envType=study-plan-v2&envId=top-interview-150

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]

 

Contraints:

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• Only one valid answer exists.
• Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity?

---

✔ 문제접근 #1 완전탐색[통과] ⭕ -> 요구사항 충족 ❌

Intuition
완전탐색을 통해 배열의 두개의 값을 골라 target값과 일치하는지 확인한다.

Algorithm
완전탐색으로 두개의 인덱스를 선택하여 target과 일치하면 반환한다.

    def twoSum(self, nums: List[int], target: int) -> List[int]:
        
        n = len(nums)
        for i in range(n):
            for j in range(i + 1, n):
                if nums[i] + nums[j] == target:
                    return [i, j]

실행결과

Complexity Analysis

• 시간 복잡도 : O(N**N)
  • index i 탐색 O(N)
  • index j 탐색 O(N)
  • 그러므로 전체시작복잡도 : O(N**N)

• 공간복잡도 : O(1)

---

✔ 문제접근 #2 해시[통과] ⭕ -> 요구사항 충족

Intuition
전체 배열을 순회하며 dict(해시테이블)자료구조에 해당값과 그위치(index)를 key - value쌍으로 기록한다.

Algorithm

dict()자료구조 h를 선언한다.

nums배열의 각 요소를 순회하는데 만약 target에서 자신을 뺀 값이 h에 존재한다면, 조건을 충족하기 때문에 자신의 인덱스와, 더했을 때 target이 되는 숫자의 인덱스를 h에서 꺼내와 반환한다.

그러한 숫자가 없다면 h에 자신의 값을 key, 그리고 자신의 위치(index)를 value로 하여 저장한다.

    def twoSum(self, nums: List[int], target: int) -> List[int]:
        
        # [2, 7, 11, 15]
        # {data : index} = {2 : 0, 7 : 1, 11 : 2 ...}
        h = dict()
        for i in range(len(nums)):
            elem = nums[i]
            if target - elem in h:
                return [h[target - elem], i]
            
            h[elem] = i

실행결과

Complexity Analysis

• 시간 복잡도 : O(N)
  • 배열을 순차탐색 O(M)
  • dict자료구조의 in연산 O(1)
  • 그러므로 전체시작복잡도 : O(N * 1) = O(N)

• 공간복잡도 : O(N)
  
  • 추가적인 dict자료구조 사용

---

기타풀이 및 회고

해당 문제는 배열에서 같은 값이 두번이상 등장하지 않기 때문에 가능한 방법이다. 만약 배열안에 같은 값이 여러번 등장했다면 dict(해시)에서 충돌이 일어날 것이므로 문제를 해결할 수 없다.

또한 정답이 유일하게 한개 주어짐이 확실시 되기때문에 정답이라고 판단되면 곧바로 return할 수 있었다.

 

요구사항에 따라 사용할 수 있는 알고리즘인지 아닌지 확실한 판단이 필요하다.