[배열] 두 수의 합

* leetcode 1. Two Sum

 

Q. 덧셈하여 타겟을 만들 수 있는 배열의 두 숫자 인덱스를 리턴하라.

# 입력
nums = [2, 7, 11, 15], target = 9

# 출력
[0, 1]

---

풀이 1. Brute-Force 계산

# 모든 경우의 수 계산
def twoSum(self, nums: List[int], target: int) -> List[int]:
    for i in range(len(nums)):
        for j in range(i+1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]

 

풀이 2. in을 이용한 탐색

# 첫번째 풀이와 동일한 시간 복잡도 O(n^2)이지만 상수항이 이전에 비해 작아서 더욱 빠르다.
def twoSum(self, nums: List[int], target: int) -> List[int]:
    for i, n in enumerate(nums):
        complement = target - n
        
        if complement in nums[i + 1:]:
            return nums.index(n), nums[i + 1].index(complement) + (i + 1)

 

풀이 3. 첫 번째 수를 뺀 결과 키 조회

# 딕셔너리는 해시 테이블로 구현되어 평균적으로 O(1)에 가능하다. 따라서 전체 시간 복잡도는 O(n)이 된다.
def twoSum(self, nums: List[int], target: int) -> List[int]:
    nums_map = {}
    
    # 카와 값을 바꿔 딕셔너리로 저장
    for i, num in enumerate(nums):
        nums_map[num] = i
        
    # 타겟에서 첫 번째 수를 뺀 결과를 키로 조회
    for i, num in enumerate(nums):
        if target - num in nums_map and i != nums_map[target - num]:
            return nums.index(num), nums_map[target - num]
            
            
"""
조회 구조 개선
"""
def twoSum(self, nums: List[int], target: int) -> List[int]:
    nums_map = {}
    
    for i, num in enumerate(nums):
        if target - num in nums_map:
            return [nums_map[target - num], i]
        nums_map[num] = i

 

풀이 4. 투 포인터 이용

"""
간단하게 풀이할 수 있지만, 해당 문제는 nums가 정렬된 상태가 아니기 때문에 이 풀이법을 사용하려면
정렬이 필요하다. 하지만, nums를 정렬하게 되면 인덱스가 꼬이기 때문에 이 풀이법은 사용할 수 없다.
"""
def twoSum(self, nums: List[int], target: int) -> List[int]:
    left, right = 0, len(nums) - 1
    
    while not left == right:
        # 합이 타겟보다 크면 오른쪽 포인터를 왼쪽으로
        if nums[left] + nums[right] > target:
            right -= 1
        
        # 합이 타겟보다 작으면 왼쪽 포인터를 오른쪽으로
        elif nums[left] + nums[right] < target:
            left += 1
            
        else:
            return left, right