[leetcode | 파이썬] Two Sum

Description

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.

• 한국어 ver. 정수 배열 nums와 정수 target이 주어지면, 더해서 target이 되는 두 숫자의 인덱스를 반환하는 프로그램을 작성하세요. 단, 각 입력에는 정확히 하나의 솔루션이 있으며, 동일한 요소를 두 번 사용하지 않아야 합니다. 반환하는 인덱스의 순서는 상관없습니다.
  

Example

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].

Solution 1 - Brutal Force

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

• 풀이 설명 이중 for문을 사용해 리스트 내 숫자를 더한다. 바깥쪽 for문은 더하기의 기준이 된다. 안쪽 for문은 기준이 되는 요소에 더해지는 요소를 의미한다. 리스트의 i번째 요소를 기준으로, i번째 요소와 그 다음의 요소들(j번째 요소들)을 더해 target이 나오면 해당 인덱스를 반환한다.
  

Solution 2 - Hash Table

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        differences = {}
        for index, number in enumerate(nums):
            diff = target - number

            if diff in differences: 
                return [index, differences[diff]]
            else:
                differences[number] = index

• 풀이 설명
  1. dictionary(hash table)을 생성해둔다.
  2. nums리스트를 돌면서 target과 nums리스트 요소의 차(diff) 를 구한다.
  3. diff 라는 key가 dictionary에 있는 경우 현재 비교대상인 숫자의 인덱스와 key의 value(인덱스)를 반환한다.
  4. 그러한 key가 없는 경우 숫자를 key로, 인덱스를 value로 하여 dictionary에 추가해둔다.