[Leetcode, Solution] 1. Two Sum 문제풀이

Leetcode 사이트의 알고리즘 문제를 풀어본 뒤 올리는 풀이입니다.

문제

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 <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• Only one valid answer exists.

Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity?

요약하면 입력값으로 숫자로 이루어진 리스트와 target 숫자를 입력받습니다.
리스트의 두가지 요소를 합하면 target 숫자가 되는데 몇번째 인덱스 숫자인지 찾아내는 문제입니다.

기본적으로 가장쉽게 생각할 수 있는건 for문을 두번 돌려서 찾아내는건데요
O(n2) 시간값이 나오면서 비효율적으로 동작하게됩니다.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for first_index, first_num in enumerate(nums):
            for second_index, second_num in enumerate(nums[first_index+1:], first_index+1):
                if first_num + second_num == target:
                    return [first_index, second_index]

이를 좀더 효율적으로 풀기 위해서는 해시테이블을 사용합니다.

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        hash_table = dict()

        for i, num in enumerate(nums):
            try:
                hash_table[target - num]
                return [hash_table[target - num], i]
            except KeyError:
                hash_table[num] = i

위 코드로 실행했을 경우 결과입니다.

55 / 55 test cases passed.
Status: Accepted
Runtime: 42 ms
Memory Usage: 14.4 MB
Submitted: 1 minute ago

더 좋은 아이디어나 추가로 수정해야하는 부분이 보이시면 댓글남겨주시길 바랍니다.
감사합니다.