LeetCode Two Sum - Python

LeetCode 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.

Constraints

• 2 <= nums.length <= $10^4$
• $-10^9$ <= nums[i] <= $10^9$
• $-10^9$ <= target <= $10^9$
• Only one valid answer exists.

Approach

1. 주어진 nums 배열에서 숫자를 하나씩 꺼낸다.
2. target에서 nums 배열에서 꺼낸 숫자를 빼서 얼마를 더해야 target이 될지 확인한다.
3. nums에서 꺼낸 숫자의 인덱스 값 이후에 찾아야 할 숫자가 있는지 확인한다.
4. 있다면 nums에서 꺼낸 숫자의 인덱스와 찾은 숫자의 인덱스를 반환한다.
5. 없다면 2 ~ 3을 반복한다.

Complexity

• Time complexity:
• 바깥 for 문에서 $O(n)$
• nums[index + 1] 탐색에서 $O(n)$

• 따라서, 최악의 경우 시간 복잡도는 $O(n^2)$

• Space complexity:
• $n$이 커지면 할당된 메모리도 커지는 변수는 없으므로 공간 복잡도는 $O(1)$

Code

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for index, num in enumerate(nums):
            finding_number = target - num

            if finding_number in nums[index + 1:]:
                return [index, nums.index(finding_number, index + 1)]

개선할 점

• 해시맵을 사용하면 공간복잡도는 $O(n)$으로 늘어나지만 시간복잡도를 $O(n)$으로 줄일 수 있다.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        num_map = {}

        for index, num in enumerate(nums):
            finding_number = target - num

            if finding_number in num_map:
                return [num_map[finding_number], index]

            num_map[num] = index