LeetCode : 1

Daehwi Kim·2020년 8월 9일

leetcode

LeetCode

목록 보기

7/23

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