Hashmap: 1. Two Sum ★

1. Two Sum

 

최초 내 코드

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

 

 풀리긴 하지만, 아~ 주 비효율적임

 

https://youtu.be/KLlXCFG5TnA?si=hamrAV8oUfPTDA7b

 

https://youtu.be/zH7F-qnTi74?si=lBLzCWaIWbKt4kxF

 

 

해시맵 으로 풀자~

 

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # Initialize an empty hashmap to store number and its index
        # 숫자와 그 인덱스를 저장할 빈 딕셔너리 생성
        hashmap = {}  # key: 숫자, value: 인덱스

        # Populate the hashmap with the numbers and their indices
        # 숫자와 해당 인덱스를 hashmap에 저장
        for idx, num in enumerate(nums):
            hashmap[num] = idx  # 현재 숫자를 키로, 인덱스를 값으로 저장

        # Iterate through the nums array to find the solution
        # nums 배열을 순회하여 두 수의 합이 target인 경우 찾기
        for idx, num in enumerate(nums):
            # Calculate the difference needed to reach the target
            # 현재 숫자와 target의 차이를 계산
            diff = target - num

            # Check if the difference exists in the hashmap and is not the same index
            # 차이가 hashmap에 존재하며, 현재 인덱스와 다를 경우 확인
            if diff in hashmap and hashmap[diff] != idx:
                # Since each input has exactly one solution, return immediately
                # 입력은 항상 하나의 정답만 존재하므로, 바로 결과를 반환
                return [idx, hashmap[diff]]

        # No need for additional return statement since the problem guarantees a solution
        # 문제 조건상 항상 정답이 존재하므로 추가적인 반환은 필요 없음

 

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

        for idx, num in enumerate(nums):
            hashmap[num] = idx

        res = []
        for idx, num in enumerate(nums):
            diff = target - num

            if diff in hashmap and hashmap[diff] != idx:
                # each input would have exactly one solution
                # 오직 1개 답만 있으니, 나오면 바로 리턴
                return [idx, hashmap[diff]]

 

최종 코드 

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # 두개 더해서 target 이 되는 index 찾기.
        # 그런데, 1개 정답만 있음
        # 해시맵 사용해서 쉽게 구하자: {배열 값: 배열index}
        hashmap = {}
        for idx, n in enumerate(nums):
            hashmap[n] = idx
        
        for n, idx in hashmap.items():
            diff = target - n
            if diff in hashmap and idx != hashmap[diff]:
                return [idx, hashmap[diff]]

 

이렇게하면 Input: nums = [3,3], target = 6 Output: [0,1] 이 경우는 안됨!!

 

맞아요! 👀 지금 코드에서는 문제 조건을 완전히 만족하지 않아요. 특히 nums = [3, 3], target = 6 같은 입력에서는 i != j 조건을 만족해야 하는데, 현재 hashmap이 같은 값일 때 마지막 인덱스만 저장해서 하나가 덮어써지기 때문이에요.

---

🔍 문제점 요약:

for idx, n in enumerate(nums):
    hashmap[n] = idx

 

이 코드에서 nums = [3, 3]이면
hashmap = {3: 1} ← 인덱스 0이 덮여짐

그러면 나중에 diff = 3을 찾을 때도 [1, 1]을 찾게 되어 i != j 조건 위반

 

✅ 해결법:

for 루프 하나로, 해시맵을 순차적으로 채우면서 정답을 찾는 구조로 바꿔야 해요:

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashmap = {}  # {값: 인덱스}
        for idx, n in enumerate(nums):
            diff = target - n
            if diff in hashmap:
                return [hashmap[diff], idx]
            hashmap[n] = idx

💡 예시 동작 (nums = [3, 3], target = 6)

1. idx = 0, n = 3, diff = 3 → hashmap = {} → diff 없음 → hashmap = {3: 0}
2. idx = 1, n = 3, diff = 3 → diff 3 있음! → return [0, 1]