Leetcode-easy-1.Two Sum

1. 첫번째 코드

- O(n^2)

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        # 맨 앞의 element부터 차례대로 더한 후 맞는 값 return
        idx = 0
        while idx < len(nums):
            num = nums[idx]
            for i in range(idx+1, len(nums)):
                if num + nums[i] == target:
                    return [idx, i]
            idx += 1

 

2. 두번째 코드

- Hash Table 이용

'''
x를 고정하고 target-x가 존재하는지 확인
존재하면 index return
'''

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        dic = {}
        i = 0
        for num in nums:
            if target - num in dic:
                return dic[target - num], i
            dic[num] = i
            i += 1