Two Sum

출처

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

문제

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.

예시

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

답1

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

그냥 왼쪽에서 오른쪽으로 사사사삭 루프 돌면서 비교했다(이중루프)

답2

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

이거는 반대로 오른쪽에서 왼쪽으로 사사삭 루프 돌면서 비교하는건데, 재미있는점은 오른쪽으로 가면서 Dictionary에 값을 저장해 두면 다시 왼쪽에 그 값이 있는지 찾기위해 루프를 돌 필요가 없다는것이다. 답1처럼 푸는것보다 150배정도 빠르다. 대신 메모리는 0.5MB더 사용했다.

댓글 남기기

이메일은 공개되지 않습니다. 필수 입력창은 * 로 표시되어 있습니다

Up Next:

군대를 오다

군대를 오다