LeetCode - 1. Two Sum

[LeetCode] 1. Two Sum

LeetCode 1번 문제를 풀어보았다.. Link

Problem

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.

Intuition

Brute force를 사용하여 nums의 모든 수의 조합과 Target이 같은지 확인한다면 풀리는 문제라고 생각하였다.

Approach

1. nums의 i번째 수와 i+1번째 수를 더하고 target과 같은지 비교한다.

2. i+1가 n이 될 때 까지 반복한다.

3. i가 n-1이 될 때 까지 반복한다.

Complexity

• Time complexity:

  nums의 각 요소에 나머지 배열을 반복하기 때문에 \(O(n^2)\)

• Space complexity: \(O(1)\)

My Code

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

Others

이건 Dictionary를 사용하는 풀이법인데, Dictionary에서 target까지의 complement가 되는 수를 탐색하는 방법으로,

시간복잡도를 \(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]]