[LeetCode] #1 Two Sum

난이도: Easy
문제 링크: https://leetcode.com/problems/two-sum/

1차 시도

조합 생성 시 자주 이용되는 itertools의 combinations를 이용했다.
test case는 무난하게 통과했지만, 시간복잡도가 높아 input길이가 길어지면 LeetCode에서 'time limit exceeded'가 뜨면서 submit이 진행되지 않았다.

from itertools import combinations

class Solution:
    def twoSum(self, nums, target: int):
        combs = list(combinations(nums, 2))

        # #make a list of every possible answer
        answers = [sum(a) for a in combs]

        # make a hash table for every possible solution
        answer_dict = {}
        i = 0
        for answer in answers:
            answer_dict[answer] = combs[i]
            i += 1

        answer_comb = answer_dict[target]
        a = nums.index(answer_comb[0])
        nums.remove(answer_comb[0])
        b = nums.index(answer_comb[1]) + 1 #compensates for the removed number

        return [a,b]
        

시간복잡도 줄이기 (Time Limit Exceeded 해결하기)

-> 이때부터 머리를 싸매기 시작했다..
아마 O(n제곱) 미만으로 풀어야 하는 문제 같았다.

itertools.combinations() 메소드의 경우 시간복잡도가 O(n! / (n-r)! / r!) 인데, n이 커질수록 시간복잡도가 급격하게 증가하기 때문에, 2 <= nums.length <= 10**4 인 문제의 조건 상 활용하기 어려웠다. (nums.length가 인풋 길이)

그렇다면... 어떻게 target이 두 숫자의 sum과 일치하는지 알 수 있을까?

*아래 내용은 LeetCode의 공식 풀이를 참고했다.

1. Hash table을 만들면 index 검색 시간을 줄일 수 있다 (O(1))
   -> nums 리스트를 활용해 key=리스트의 값, value = 리스트의 index값인 hash table을 만들어준다.
2. for문을 사용해 nums 리스트를 순회한다 (O(n))
   -> 이 때 target값을 활용해 현재 순회하는 값에 대응하는 complement값을 만들어준다.
   말이 어렵지만, complement = target-nums[i] 이런 식으로 만들어줄 수 있다.
3. if 문으로 complement값이 해시 테이블에 존재하는지 검사한다. (이 때 같은 값을 두 번 사용할 수 없다는 문제의 조건 상, hashmap[complement], 즉 complement의 index값이 i 값과 같을 수 없다.)

완성 코드

class Solution:
    def twoSum(self, nums, target: int):
        hashmap = {num:nums.index(num) for num in nums}
        for i in range(len(nums)):
            complement = target-nums[i]
            if complement in hashmap and i != hashmap[complement]:
                return [i, hashmap[complement]]