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

 

처음시도

from itertools import permutations
from typing import List
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        permu_idx=list(permutations(range(len(nums)),2))
        for i in permu_idx:
            if nums[i[0]]+nums[i[1]]==target:
                return [i[0],i[1]]

 

아무생각없이 permutations 사용해서 품 -> 당연하게 시간초과

 

두번째 시도코드가 날라갔지만nums의 각각 원소에 대해 합이 target이 되는 값을 이진 탐색으로 찾으려함-> 시간복잡도 O(NlogN)

 

정답:Hash table 즉 파이썬의 Dict를 사용함

from typing import List
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        seen={v:i for i,v in enumerate(nums) }
        for idx,v in enumerate(nums):
            if target-v in seen and seen[target-v] != idx:
                return [seen[target-v],idx]
        

이는 Two-pass Hash table 이라 부름

처음 key가 nums list 값들 그의 index 값이 value인 dict를 만들어줌

만약 target-v값이 dict에 있고 그 idx가 겹치치 않는다면 return해준다.

Two-pass Hash table

 

from typing import List
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        seen={}
        for idx,v in enumerate(nums):
            find_n=target-v
            if find_n in seen:
                return [seen[find_n],idx]
            seen[v]=idx
                
        

이 방법은 One-Pass Hash table

명칭의 의미는 정확히 모르지만 for문을 한번만 써서 그런것 같다.

이는 위에 two pass hash table에서 사용했던 dict를 처음에 바로 만드는 것이 아니라 차례차례 뒤져가며 함.

-> index가 중복될 우려 안해도됨

-> dict를 전부 완성시키지 않고도 답을 찾을수 있기 때문에 효율적

One-pass Hash table

하지만 결과는 거의 비슷하게 나오는것으로 보아 큰 차이는 아닌듯함