LeetCode Top Interview 150) Two Sum

Question

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.

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

---

---

정렬되지 않은 정수 리스트 nums가 있고, 합이 target값과 같은 특정 원소 2개의 인덱스를 리스트에 담아서 반환하는 문제입니다. 조건에서 항상 답이 존재한다고 했으므로 예외처리에 신경쓸 부분도 없습니다.

제가 생각한 코드는 다음과 같습니다.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        d = {}
        for idx,num in enumerate(nums):
            if num in d:
                return [d[num],idx]
            d[target-num] = idx

• d : (target-정수) : 정수의 인덱스 키값을 가지는 딕셔너리 입니다.
• nums를 순회하다가 d가 원소num을 가지면 두 인덱스를 반환합니다.
  • 순회할 때 마다 d에 (target-정수) : 정수의 인덱스 를 저장합니다.
    • target-정수값이 이후 원소에 존재하는지 확인하기위한 키입니다.
    • 인덱스는 원하는 원소쌍이 나타났을 때 인덱스를 바로 확인하기 위한 값입니다.

---

알고리즘이 어렵지 않지만 초반에 고민을 조금 해본 문제입니다. 그래도 천천히 조건을 맞춰나가면 해결책이 나타났습니다.

문제 조건상 한 번의 탐색으로 마무리를 지어야 하고 모든 원소의 쌍이 확인되어야 하므로 앞의 값을 저장해야 합니다. 이 때 저장하는 방식은 원소 값도 괜찮지만 target-원소값으로 저장하여 뒤의 숫자와 곧바로 비교될 수 있도록 저장했습니다.

만약 존재 여부만 필요했다면 딕셔너리가 아닌 집합을 사용했을 것입니다. 하지만 인덱스가 필요한 상황이므로 딕셔너리로 정의하여 각 인덱스까지 저장을 했습니다.

천천히 생각하면 빨리 풀 수 있는 문제였습니다.

• 메모리 사용률이 왜 높은지 생각해봐도 모르겠어서 솔루션들을 참고해보니.. 이중 반복문으로 시간복잡도는 내려놓은 솔루션이 상위권에 있어서 그런 듯 합니다. 값을 저장할 필요가 없어선지 메모리 사용률이 좋게 나옵니다. 근데 그런 풀이가 통과돼도 되나..;