Problem

• Given an array of integers, return indices of the two numbers such that they add up to a specific target.

• You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example

---

Solution

solution 1

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)):
                if nums[i] + nums[j] == target:
                    return [i, j]

runtime : 6272 ms

• 무차별 대입 방식인 Brute-Force(브루트 포스)로 풀었다.
• 풀이 시간 복잡도가 O(n2)으로 굉장히 비효율적인 풀이이다.

solution 2

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        
        for inde, num in enumerate(nums):
            complement = target - num
            
            if complement in nums[inde+1:]:
                return nums.index(num), nums[inde+1:].index(complement) + (inde +1)

runtime : 1096 ms

• In을 이용하여 탐색을하여 Brute-Force방식에 비해 6배정도 성능이 좋아졌다.
• 파이썬 내부 함수로 구현된 In은 매번 값을 비교하는 것에 훨씬 더 빨리 실행된다.

solution 3

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        nums_map = {}
        
        for i, num in enumerate(nums):
            nums_map[num] = i
            
        for i, num in enumerate(nums):
            if target - num in nums_map and i != nums_map[target - num]:
                return nums.index(num), nums_map[target - num]

runtime : 48 ms

• 딕셔너리에 키와 인덱스를 바꿔서 저장하고, 타겟에서 첫 번째수를 빼서 두번째 수를 키로 조회하여 인덱스를 알아내는 풀이방법이다.
• 딕셔너리는 해시테이블로 구현되어 있어서 평균적으로 O(1)이다.

solution 4

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        nums_map = {}
        
        for i, num in enumerate(nums):
            if target - num in nums_map:
                return [nums_map[target - num], i]
            nums_map[num] = i

runtime : 52 ms

• 딕셔너리 저장과 조회를 2개의 for문으로 각각 처리했던 방식을 좀 더 개선해서 하나의 for문으로 합쳤다.
• 성능상의 이점은 없지만 코드는 한결 간결해졌다.

마지막

• 문제 자체는 쉽지만 엇떻게하면 성능을 빠르게 해야되는지 생각하게되는 문제라서 쉽지 않은 것 같다.