Two Sum(python)

in Algorithm on Algorithm, Leetcode, 완전 탐색, Python

참고 자료

leetcode - 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]
Output: 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 <= 103
  • -109 <= nums[i] <= 109
  • -109 <= target <= 109
  • Only one valid answer exists.

나의 생각

target보다 큰 수가 있으면 스킵을 하기 위해서 정렬을 하고, 작은 수 부터 차례대로 계산하려고 했다.
하지만 이전의 인덱스를 기억해야 하므로 정렬은 포기했다.
이후 이중 for문을 돌면서 target 값에서 두 수를 빼서 0이 되는 경우를 찾으려고 했다.

코드

  • 제일 비효율적인 방법
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums) - 1):
            t = target - nums[i]
            for j in range(i + 1, len(nums)):
                if t - nums[j] == 0:
                    return [i, j]
  • in을 활용한 완전 탐색
    시간 복잡도는 위와 같지만 n은 파이썬 레벨에서 매번 값을 비교하는 것에 비해 빨리 실행된다.
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i, n in enumerate(nums):
            t = target - n
            if t in nums[i + 1:]:
                return nums.index(n), nums[i + 1 :].index(t) + (i + 1)
  • 해쉬 테이블을 이용.
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        nums_map = {}
        for i, n in enumerate(nums):
            if target - n in nums_map:
                return [nums_map[target - n], i]
            nums_map[n] = i