문제 링크 https://leetcode.com/problems/two-sum/

Step1. 문제 이해하기

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]
Output: 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]

Constraints

• 2 <= nums.length <= 10^4
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• 단 하나의 정답만 존재한다.

만들어야 할 함수를 정의해보자

• nums라는 integer 배열과 target이라는 integer 값을 인자로 받고 nums의 i번째 값과 j번째 값의 합이 target 값과 같을시 [i,j] Return한다.
• 인자로 주어지는 nums 배열의 최대 개수가 10^4 까지 주어지므로, O(N^2) 미만의 시간복잡도를 갖는 풀이방법이어야 한다.

Step2. 접근 방법 생각해보기

• 완전 탐색 (Brute Force) 하면 되지 않을까?
  • 2중 반복문을 통해 Element들 끼리 모두 더하여 target과 같은지 확인하다가, 같다면 해당 element들의 [i,j]를 리턴
    • 하지만 이 방법은 2중 반복문을 통하며, Worst case일 때 시간복잡도 O(N^2)가 된다.
    • nums.length 가 10^4 일 경우, O(N^2)의 시간복잡도는 시간초과 가능성이 높으므로 시간복잡도를 개선한 풀이어야한다.
  • 시간복잡도를 더 개선할 수 있는 방법은 무엇이 있을까?
    • sort & pointer 를 이용할 수 있겠다
    • Hash Table 을 이용할 수 있겠다

Step3. 코드 설계 & 구현

1. sort를 이용한 방식

정렬을 사용.
시간 복잡도 : O(nlogn)

class Solution(object):
    def twoSum(self, nums, target):
        answer = []
        # 인자로 받은 숫자들을 오름차순으로 정렬한뒤,
        sorted_nums = sorted(nums)
        # 가장 왼쪽 / 가장 오른쪽의 포지션을 설정해준다
        left, right = 0, len(sorted_nums) - 1
        
        # left 와 right 포지션이 서로 교차될 때 까지 반복
        while left < right:
            if sorted_nums[left] + sorted_nums[right] == target:
                # left가 가리키는 값과 right가 가리키는 값을 더해 주어지는 target과 값이 같다면, 해당 element를 정답 리스트에 추가하며 반복문 탈출
                answer.append(sorted_nums[left])
                answer.append(sorted_nums[right])
                break
            elif sorted_nums[left] + sorted_nums[right] > target:
                # left가 가리키는 값과 right가 가리키는 값이 target 보다 크다면, right 포지션을 왼쪽(<)으로 이동
                right -= 1
            elif sorted_nums[left] + sorted_nums[right] < target:
                # left가 가리키는 값과 right가 가리키는 값이 target 보다 작다면, left 포지션을 오른쪽(>)으로 이동
                left += 1
        # return 해야하는 값은 더해서 target이 되는 2개의 Element의 값이 아니라,
        # 원래 인자로 주어졌던 nums 리스트에서 2개의 값이 어디에 위치하고 있는건지 즉, Position의 리스트를 return 해야하므로,
        # 리스트 컴프리헨션을 통해 정답 element 2개의 index를 리스트로 반환 
        return [i for i, num in enumerate(nums) if num in answer]

2. Hash Table을 이용한 방식

Hash Table 을 사용.
시간 복잡도 : O(N)

class Solution(object):
    def twoSum(self, nums, target):
        # 딕셔너리 자료형 생성
        dictionary = {}
        for i, num in enumerate(nums):
            if num not in dictionary:
       			# 해당 num 값이 딕셔너리에 Key로 없다면,
                # nums를 순회하며, 각 Element 에서 더해야 할 값(gap)을 구한다.
                gap = target - num
                # 딕셔너리에 gap 값을 Key로, 현재 position을 value로 등록
                dictionary[gap] = i
            else:
                # 해당 num 값이 이미 딕셔너리에 Key로 있다면 (== 어떤 element의 gap 값과 일치하는 num일 경우) ,
                # 현재 반복문의 Position & 딕셔너리에서 Key 값으로 받아온 Position이 정답이므로 해당 값들을 리턴
                return [i, dictionary[num]]