FilesExpand file tree

 main

/

YOOHYOJEONG.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

24 lines (18 loc) · 822 Bytes

 main

/

YOOHYOJEONG.py

Top

File metadata and controls

• Code
• Blame

24 lines (18 loc) · 822 Bytes

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

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

# class Solution(object):

# def twoSum(self, nums, target):

# for i in range(len(nums)):

# for j in range(len(nums)):

# if nums[i]+nums[j] == target:

# if i != j:

# return [i, j]

# > 해당 방식 사용 시 시간 복잡도가 O(n²)이라 개선을 해 보고자 아래 솔루션으로 재풀이 진행

class Solution(object):

def twoSum(self, nums, target):

seen = {}

for i, num in enumerate(nums):

diff = target - num

if diff in seen:

return [seen[diff], i]

seen[num] = i

# index를 기억하도록 하면 반복문 한번 O(n), 딕셔너리 조회 평균 O(1)로 전체 O(n)이 됨