[LeetCode 1] Two Sum

https://leetcode.com/problems/two-sum/description/

 

문제설명

정수로 구성된 리스트가 주어질 때, 두개의 숫자를 더해 target이 되는 인덱스를 반환

 

 

문제해결

2중 for문

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)-1):
            for j in range(i+1, len(nums)):
                if nums[i]+nums[j] == target:
                    return [i, j]

 

 

 

백트래킹

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        def backtrack(curr, cur_i):
            # base case
            if len(curr) == 2:
                if nums[curr[0]] + nums[curr[1]] == target:
                    return True
                else:
                    return False
            # repeat
            for i in range(cur_i, len(nums)):
                curr.append(i)
                if backtrack(curr, i+1):
                    return curr
                curr.pop()

        return backtrack([], 0)

 

 

 

투포인터

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i, num in enumerate(nums):
            nums[i] = [num, i]
        nums.sort()

        l = 0
        r = len(nums)-1

        while l < r:
            if nums[l][0] + nums[r][0] == target:
                return [nums[l][1], nums[r][1]]
            elif nums[l][0] + nums[r][0] < target:
                l += 1
            else:
                r -= 1

• 투포인터를 사용하려면 리스트가 정렬되어 있어야 하는데 문제에서 주어지는 리스트는 정렬된 리스트가 아니다. 
• 그렇다고 정렬을 해서 인덱스를 구하기에는 원래 리스트의 인덱스가 반환되지 않는다. 
• 따라서 정수와 인덱스를 모두 포함하는 리스트로 새로 구성한 다음 정렬 후 조건에 맞는 l과 r을 구한다.
• 마지막으로 l과 r번째 인덱스의 두번째 값이 실제 인덱스이므로 이를 반환한다. 

 

 

 

해싱

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hash_table = {}
        for i in range(len(nums)):
            if target-nums[i] in hash_table:
                return [hash_table[target-nums[i]], i] 
            else:
                hash_table[nums[i]] = i