FilesExpand file tree

 main

/

heypaprika.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

30 lines (26 loc) · 1.02 KB

 main

/

heypaprika.py

Top

File metadata and controls

• Code
• Blame

30 lines (26 loc) · 1.02 KB

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

25

26

27

28

29

# 2Sum을 활용한 풀이

# Note : 정렬 후 푸는 것이 더 직관적이고, 빠름

"""

복잡도 : 예상 -> 예상한 이유

시간 복잡도 : O(n^2) -> nums 배열 2중 for문

공간 복잡도 : O(n) -> 최악의 경우 nums 배열 길이만큼의 딕셔너리 생성

"""

class Solution:

def threeSum(self, nums: List[int]) -> List[List[int]]:

ans_list = set()

added_pair = {}

for target_i, target_number in enumerate(nums):

cur_ans_list = []

num_dict = {}

if target_number in added_pair:

continue

for i in range(target_i + 1, len(nums)):

num_A = nums[i]

num_B = - target_number - num_A

if num_B in num_dict:

cur_ans_list.append(sorted([target_number, num_A, num_B]))

added_pair[target_number] = num_A

num_dict[num_A] = 1

for item in cur_ans_list:

ans_list.add(tuple(item))

return list(ans_list)