1. Two Sum

1. Description

• Given an array of integers nums and an integer target, return the indices i and j such that nums[i] + nums[j] == target and i != j.
• You may assume that every input has exactly one pair of indices i and j that satisfy the condition.
• Return the answer with the smaller index first.

2. Example

Example 1

Input: nums = [3,4,5,6], target = 7 Output: [0,1]

Example 2

Input: nums = [4,5,6], target = 10 Output: [0,2]

Example 3

Input: nums = [5,5], target = 10 Output: [0,1]

3. Solution

• 📌이번 문제는 친구(광성)이가 전에 말했던 투 포인터를 사용해서 쓸 생각을 했었다.
  • 내가 이해한 투 포인터가 맞는지는 잘모르겠지만
    • 배열의 처음과 뒷부분을 지정해서 뒷부분 인덱스를 하나씩 줄여서 비교해가는걸 생각했다.
  • 이후 코드를 짰으나 Brute Force 방법으로 하게 되는거라 다른 방법을 찾아보았다.
    • 스택을 이용해 첫번째 인덱스 값을 넣고 이후 위의 투 포인터방식과 비슷하게 값을 비교해서 넣는 방식으로 생각했지만 그저 시간복잡도가 더 큰 코드가 되었다.
• 이후에 구글에 검색해서 여러 답지들을 확인하고 enumerate를 사용해서 딕셔너리로 푸는 방법을 알게 되었다. (거의 전부 딕셔너리로 hash table을 만들어 풀었다.)

1. 첫번째 풀이
   • runtime: 0ms
   • 설명
     • 빈 딕셔너리를 하나 만든다.
     • enumerate함수를 사용하여 배열의 인덱스와 값을 나눈다.
     • target에서 값을 빼서 나오는 value가 결국에는 배열에 있는 값이랑 같으면 인덱스를 출력하는 방법이다.
     • value값이 딕셔너리 num_dict에 있다면 [num_dict[value],i]를 리턴
     • 아니면 num_dict[num] = i로 인덱스 값을 저장한다.
     • 이후 for문을 돌면서 값을 찾는다.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        num_dict = {}
 
        for i, num in enumerate(nums):
            value = target - num
            if value in num_dict:
                return [num_dict[value], i]
            num_dict[num] = i
        return []

• 📌enumerate함수는 순서가 있는 자료형을 입력으로 받았을 때, 인덱스와 값을 포함하여 리턴
• 📌dictionary의 키 값을 가져 올때 대괄호를 사용하여 값을 불러올 수 있다.

4. What I Learned

References

• 정답지 1
• 정답지 2
• enumerate 함수
• 딕셔너리 값 가져오기