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
        # 문제 조건상 항상 정답이 존재하므로 추가적인 반환은 필요 없음