[leetcode-1] Two Sum

LeetCode-1

Two Sum : target과 일치하는 리스트 두개의 합

note : O

MyAnswer (O(n * n))

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
    len_nums = len(nums)
    if len_nums==2:
        return [0,1]
    for i in range(len(nums)):
        for j in range(i+1,len(nums)):
            if target==(nums[i]+nums[j]):        
                return [i, j]

Result : 3649ms Memory: 14.9mb

Answer O(n * n) (in의 시간 복잡도 n)

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

Result : 606ms Memory: 15mb

Answer O(n)

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
    d = {}
    for i, j in enumerate(nums):
        r = target - j
        if r in d: return [d[r], i]
        d[j] = i
    # An Upvote will be encouraging