LeetCode- TwoSum

Two Sum

LeetCode - The World's Leading Online Programming Learning Platform

문제의 핵심

합이 특정 값이 되는 두 수를 O(n)에 찾을 수 있는지?

O(n^2)

class Solution(object):
    def twoSum(self, nums, target):

        length = len(nums)
        fin=False
        for i in range(0,length):
            for j in range(i+1, length):
                s = nums[i]+nums[j]
                if(s==target):
                    return [i,j]

접근법

• 시간을 아끼려면 공간을 일부 희생해야 한다.
• O(n)에 읽으려면 한번 스캔으로 정보를 기록해야 한다.
  • 그리고 그 정보가 다음 접근 시 O(1) 이 cost가 나와야 한다. ( O(n)* O(1) 이 최종 시간복잡도가 되므로)
  • O(1) cost는 indexing 밖에 없다.
  • 따라서 스캔하면서 새로운 인덱싱을 해야 한다.
• 스캔 하면서 인덱싱을 하고, 기존 인덱싱을 확인해 답이 있는지 체크한다.

O(n)

class Solution(object):
    def twoSum(self, nums, target):

        m = {}
        i=0
        for num in nums:
            x = target - num
            if(x in m):
                return [i,m[x]]
            m[num]=i
            i+=1

반성

• O(n^2) 미만의 방법에서 가장 먼저 떠올린건 O(nlogn)인 정렬 후 이분 탐색(O(n) * O(logn)이였는데 그것보다 빠른 방법이 있었다.
• 생각을 더 넓게 가져가자