[LeetCode] 1. Two Sum (python3)

 

LeetCode Problem: https://leetcode.com/problems/two-sum/

Two Sum - LeetCode

 

1. Two Sum

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?

 

 

Solution1. Brute Force: O(n^2)

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

 

Solution2. Two-pass Hash Table: O(n)

build hash table: O(n)

look up hash table: O(1)

overall time complexity: O(n)

class Solution:
    def twoSum(self, nums: list[int], target: int) -> list[int]:
        hashmap = {}
        for i in range(len(nums)):
            hashmap[nums[i]] = i
            
        for i in range(len(nums)):
            complement = target - nums[i]
            if complement in hashmap and hashmap[complement] != i:
                return [i,hashmap[complement]]

 

Solution3. One-pass Hash Table: O(n)

build hash table: O(n)

look up hash table: O(1)

overall time complexity: O(n)

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashmap = {}
        for i in range(len(nums)):
            complement = target - nums[i]
            
            if complement in hashmap:
                return [i, hashmap[complement]]
            hashmap[nums[i]] = i

 

https://github.com/junyeollee/CODINGTEST_PRACTICE/blob/main/leetcode/%5BLeetCode%5D%201.%20Two%20Sum.ipynb

GitHub - junyeollee/CODINGTEST_PRACTICE

 

 

+) 최근에 다시 문제를 풀 기회가 있었다.

해시테이블을 사용하는 것은 동일하나 이번에는 enumerate를 사용

python에서 index를 활용하여 접근하면 그때마다 메모리를 엑세스하기 때문에 가능하면 한번의 접근으로 끝는 것이 좋아 수정

class Solution:
    def twoSum(self, nums: list[int], target: int) -> list[int]:
        hashtable = {}
        for i, num in enumerate(nums):
            complement = target - num
            
            if complement in hashtable:
                return [hashtable[complement], i]
            
            hashtable[num] = i