[Leetcode : Two Sum]

Problem

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.

• difficulty : easy

My answer_1 (2022-01-09)

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: 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]

• status : accepted
• Runtime : 3375ms
• Memory usage : 14.4MB
• Time complexity : $O(n^2)$
• Space complexcity : $O(1)$

문제 풀이 : 브루트 포스 풀이

발전 사항

1. function annotation 진행
   def twoSum(self, nums : List[int], target : int) -> List[int]:
2. Time complexity : $O(n)$이 되도록 만들기

My answer_2 (2022-03-21)

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        for i in range(len(nums)):
            counter_num = target - nums[i]
            if counter_num in nums:
                if nums.index(counter_num) != i:
                    return [i,nums.index(counter_num)]
        return []

• status : accepted
• Runtime : 807ms
• Memory usage : 14.3MB
• Time complexity : $O(n)$
• Space complexcity : $O(1)$

발전 사항

1. enumerate 사용하기
2. 마지막 return [] -> return 으로 하기
3. dictionary 사용하기

My answer_3 (2022-03-29)

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        counter = {}
        for i,n in enumerate(nums):
            if n in counter.keys():
                return [counter[n],i]
            else:    
                counter[target - n] = i
        return 

• status : accepted
• Runtime : 485ms
• Memory usage : 14.4MB
• Time complexity : $O(n)$
• Space complexcity : $O(n)$

SUMMARY

1. n개의 한정된 데이터에서 값 찾는다면, 대부분 계산이 $O(n)$으로 가능하다. 그렇게 코드를 짜도록 하자.
2. enumerate는 python에서 권장하는 내재함수. range가 더 빠르다는 말이 있지만, enumerate 쓰는게 훨씬 깔끔하다.
3. 찾고자 하는 값과 출력해야 하는 값이 다르다면 dictionary 활용을 하자.