LeetCode No.1 TwoSum

취업을 위해 LeetCode에서 알고리즘을 공부하려고합니다.
앞으로 매일 LeetCode의 Problem을 해제하고 기록합니다.

우선 Top 100 Liked Questions부터 시작하고 싶습니다.
순서는 Easy -> Medium -> Hard입니다.

그럼 오늘의 Task는 No.1 TwoSum입니다.
참고 : leetcode twosum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

답변 1
시간 계산량:O(n)
공간 계산량:O(n)

python3code

    def twoSum(self, nums: List[int], target: int):
        i = 0
        while i < len(nums):
            if i == len(nums)-1:
                return "no result"
            wanted = target - nums[i]
            rest = nums[i+1:]
            if wanted in rest:
                return [i, rest.index(wanted)+i+1]
            i = i+1

python의 list형의 특성을 이용해 list[i+1:]에서 target-nums[i]를 찾습니다.
또한 list.index()를 사용하는 것도 편리하네요.
결과는 다음과 같습니다.


답변 2

python3code

    def twoSum(self, nums: List[int], target: int):
        i = 0
        dict = {}
        while i < len(nums):
            if nums[i] in dict:
                return [dict[nums[i]], i]
            else:
                dict[target-nums[i]] = i
            i = i+1

파이썬의 사전 형식을 사용합니다. 공간 계산량이 약간 증가하지만 실행 시간이 빨라집니다.
결과는 다음과 같습니다.


이상입니다. C 언어 버전은 또한 향후 시간이 있을 때 보충합니다.