[Python-Leetcode] 1. Two Sum (difficulty : Easy - ☆)

문제설명

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.

 

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

 

Constraints:

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• Only one valid answer exists.

 

Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity?

 

문제 풀이

1) Brute Force

class Solution(object):
    def twoSum(self, nums, target):
        leng = len(nums)
        for i in range(leng):
            for j in range(i+1, leng):
                if target - nums[i] == nums[j]:
                    return [i, j]

1) 매우 직관적으로 target - num[0] = num[1], num[2], ... 일일히 확인하는 방식

매우 Compute Time이 긴 단점이 존재합니다.

일반적으로 값을 찾을 때에는 set혹은 dict 타입을 써서, if something in set or dict: 방식으로 찾는게 compute time을 줄이는데 좋을 것 같습니디.

 

 

2) Set Imprementation

class Solution(object):
    def twoSum(self, nums, target):
        ans = {}
        for idx, val in enumerate(nums):
            compute_val = target - val
            if compute_val in ans:
                return [ans[compute_val], idx]
            else:
                ans[val] = idx

 

Python Set의 경우, 어떤 Value X를 Set S에 추가할 때, Hash Function을 사용합니다.

즉, 1, 'SK', 3.5 등의 값을 Set에 추가할 때 Hash(x)의 해시 함수를 거친 값을 바구니의 번호로 리턴합니다.

여기서 x에 들어가는 1, 'SK', 3.5의 변수들은 Hashable Types이 되며, Hash(x)로 리턴되는 값은 number값입니다.

 

Immutable value들은 모두 hashable 변수로 사용할 수 있습니다.

※ string, integer, Boolean, Tuple 등

하지만 Mutable 변수 타입은 hashable 변수로 사용할 수 없습니다.

※ set, list, dictionary 등

 

Type Error (unhashable)