[leetcode] - 1. Two Sum

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.

풀이

nums 리스트 안에 두개를 합해서 target이 되는 경우가 반드시 존재한다.

나는 itertools.combinations를 활용해서 $O(n^2)$ 으로 풀었다.

from itertools import combinations

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

        for pair in combinations(range(len(nums)), 2):
            i, j = pair
            if nums[i] + nums[j] == target:
                return [i, j]

그런데 Follow-up에 $O(n^2)$ 보다 적은 시간 복잡도로 풀 수 있다고 해서 어떻게 하나 한번 찾아봤다.

방법은 target - num[i] 를 가지는 리스트를 하나 생성하는 방식인데, 공간 복잡도를 $O(n)$, 시간 복잡도를 $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]]