[LEET CODE] 1. Two Sum

배열 : 메모리 공간 기반 연속 방식의 가장 기본이 되는 자료형

         크기를 지정하고 해당 크기만큼의 연속된 메모리 공간을 할당받는 작업을 수행

         어느 위치에나 O(1)에 조회 가능

동적 배열 :  크기를 지정하지 않고 자동으로 리사이징하는 배열 ( 파이썬의 List)

                  미리 초기값을 작게 잡아 배열을 생성하고, 데이터가 추가되면서 꽉 채워지면 늘려주고 모두 복사하는 방식

                  파이썬의 Growth Factor(성장 인자)는 초반에는 2배(더블링)씩 늘려가지만 전체적으로는 약 1,123배 ( 다른언어에 비해 조금만 늘려가는 형태)

 

# Problem

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] Example 2: Input : nums = [3, 2, 4] , target = 6 Output :  [1, 2] Constraints: 2 <= nums.length <= 103 -109 <= nums[i] <= 109 -109 <= target <= 109 Only one valid answer exists.

 

같은 숫자 2개로 만들어야하는 경우 처리하기

ex) [3,3], target = 6

 

# My Answer = Solution 2

num보다 뒤에 나오는 숫자에서 찾기

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for num in nums:
            if target-num in (nums[nums.index(num)+1:]):
                 return [nums.index(num), \
                 	nums[nums.index(num)+1:].index(target-num)+nums.index(num)+1]
        

 

# Solution 1 - Brute-Force(브루트 포스)로 계산

시간복잡도 O(n²)

class Solution:
    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]

 

# Solution 2 - in을 이용한 탐색

전체 시간복잡도는 O(n²)이지만 파이썬에서 in은 훨씬 빠름

class Solution:
    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)]

 

# Solution 3 - 첫번째 수를 뺀 결과 키 조회

시간복잡도 O(n)

class Solution:
    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 [i, nums_map[target - num]]

 

# Solution 4 - 조회 구조 개선

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        nums_map = {}
        # 하나의 `for`문으로 통합
        for i, num in enumerate(nums):
            if target - num in nums_map:
                return [nums_map[target - num], i]
            nums_map[num] = i # 앞에서 부터 딕셔너리에 저장

 

# Solution 5 - 투 포인터 이용

시간복잡도 O(n)

이 문제에서는 정렬된 상태가 아니기 때문에 사용할 수 없음

class Solution:
    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:
                left += 1
            # 합이 타겟보다 작으면 왼쪽 포인터를 오른쪽으로
            elif nums[left] + nums[right] > target:
                right -= 1
            else:
                return [left, right]

 

# Solution 6 - Go 구현

Solution 3의 알고리즘을 Go로 구현 - 약 6배 성능 개선

// Go
func twoSum(nums []int, target int) []int {
    numsMap := make(map[int]int)

    // 키와 값을 바꿔서 딕셔너리로 저장
    for i, num := range nums {
        numsMap[num] = i
    }

    // 타겟에서 첫 번째 수를 뺀 결과를 키로 조회
    for i, num := range nums {
        if j, ok := numsMap[target-num]; ok && i != j {
            return []int{i, j}
        }
    }

    return []int{}
}