[Leetcode] 1.Two-sum

in Leetcode on Leetcode, 1, Two-sums


Problem

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.

Solution

1. Brute Force

For-Loop을 2번 돌아서 target이 되는 Index List를 구함

  • Time Complexity : O(N^2)
  • Space Complexity : O(1)

2. Hash Table 사용

Time Complexity를 줄이기 위해 complement가 array에 존재하는지 체크 complement가 존재하면, 그것의 index만 구하면됨.

nums를 iterate하면서 element를 Dictionay에 적재, 그리고 현재 loop 도는 element의 complement가 Dict에 존재하는지 체크

  • Time Complexity : O(1) ~ O(N)
  • Space Complexity : O(N)

CODE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
import functools
from typing import List
 
 
class Solution:
    # approach1. brute force
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        answer = []
        for idx, val in enumerate(nums):
            tmp = val
            for idx2, val2 in enumerate(nums):
                if target == tmp + val2 and idx != idx2:
                    answer.append(idx)
                    answer.append(idx2)
                    return answer
    
    # aprpoch2 .hash-table(with dict)
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # empty dict
        answer = dict()
        
        # loop nums
        for idx, val in enumerate(nums):
            # complement + val = target
            complement = target - val
            # find answer set
            if complement in answer:
                return [answer[complement], idx]
            else:
                answer[val] = idx
 
 
if __name__ == '__main__':
    '''
    example1
    Input : nums=[2,7,11,15] target=9
    Output : [0,1]
    '''
    nums = [2, 7, 11, 15]
    target = 9
    sol = Solution()
    assert sol.twoSum(nums=nums, target=target) == [0, 3]
    
    '''
    example2
    Input : nums=[3,2,4] target=6
    Output : [1.2]
    '''
    nums = [3, 2, 4]
    target = 6
    assert sol.twoSum(nums=nums, target=target) == [0, 3]
 
cs