[hash] 1. two-sum

https://leetcode.com/problems/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]

---

class Solution:
    def twoSum(self, nums, target):
        num_dict = {}  # 해시 테이블 초기화

        for i, num in enumerate(nums):  # 인덱스와 값을 동시에 얻음
            comp = target - num  # 보수 계산 (complement)
            
            if comp in num_dict:  # 보수가 해시 테이블에 있는지 확인
                return [num_dict[comp], i]  # 보수와 현재 숫자의 인덱스를 반환
            
            num_dict[num] = i  # 현재 숫자와 인덱스를 해시 테이블에 저장

        return []  # 해결할 수 없는 경우 빈 리스트 반환

 

 

 

👩‍🌾 return [num_dict[comp], i]

 

보수 comp가 해시테이블 num_dict 안에 존재한다면, 리스트[]를 리턴하는데, 두 가지를 반환한다.

num_dict[comp]와 i 이다.

num_dict[comp]는 target에서 i번째 인덱스의 값에 해당하는 요소를 뺀 값을 지닌다.

혹여 해당하는 수 조합이 없다면 마지막 return은 [] 빈 리스트로 받는다.

 

if comp in num_dict:
    return [num_dict[comp], i]

 

 

 

**comp(보수)**가 해시 테이블(num_dict)에 존재하는지 확인. 있다면, 해당 보수의 인덱스와 현재 인덱스 i를 리스트로 반환

 

예를 들어, 주어진 배열이 [2, 7, 11, 15]이고 target이 9일 때:

1. 첫 번째 숫자 2에서 보수는 9 - 2 = 7 이다.
2. 두 번째 숫자 7을 만났을 때, comp(보수)인 2가 이미 해시 테이블에 존재한다.
   • 이때 해시 테이블에 저장된 2의 인덱스는 0이다.
3. 따라서 [0, 1]을 반환한다.

 

nums = [2, 7, 11, 15]
target = 9
numMap = {2: 0, 7: 1}  # 딕셔너리 상태

complement = 2  # target - nums[i] = 9 - 7 = 2
print(numMap[complement])  # 출력: 0

 

numMap[complement] = 0  # 보수의 인덱스
i = 1  # 현재 숫자의 인덱스

print([numMap[complement], i])  # 출력: [0, 1]

 

 

*출력결과

nums = [2,7,11,15] / target = 9

Index: 0, Value: 2
Index: 1, Value: 7
Index: 2, Value: 11
Index: 3, Value: 15

 

 

❗해시에서는 값이 키로 작용하므로, 이 값(숫자)으로 접근하여 인덱스를 반환할 수 있다.

num_dict[2] = 0  # 숫자 2의 인덱스는 0
print(num_dict[2])  # 출력: 0