[Leetcode/파이썬] 1. Two Sum

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 <= 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?

 

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        num_hash = {}

        for idx in range(len(nums)) :
            num = nums[idx]
            if target - num in num_hash :
                return [idx, num_hash[target - num]]
            num_hash[num] = idx

만약 2중 포문을 생각했다면, 쉬운 문제가 되었을 것이다. 우리 한 번 고급지게 풀어보도록 하자. (사실 나도 초보자.)

이중 For문이 아니라 hash를 활용하여 문제를 풀어보자. 

일단 기본적으로 덧셈을 한 번 해보자. 문제에서 정답[0,1] 이라고 가정하면, $nums[0] + nums[1] = target$ 이 될 것이다. 이를 $nums[1] = target - nums[0]$ 으로 $nums[0]$을 각각 빼주면 이 식이 완성된다. 이를 활용하는 것이다. 

for 루프를 활용하여 idx를 받아오고 현재 수를 num으로 둔 후 target - num 이 딕셔너리 안에 있는지 탐색한다. 이때 탐색 시간 복잡도는 O(1)일 것이다. 아마 처음엔 빈 딕셔너리기 때문에 채워져야 할 텐데 hash[num] = idx 가 되도록 하여 추가한다. val이 키, idx가 값이 된다. 만약 있다면 [idx, hash[target-num]] 값을 하게 되면 두 인덱스가 return 되게 된다. 코드 참조.