forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathjongwanra.py
More file actions
106 lines (84 loc) ยท 2.87 KB
/
jongwanra.py
File metadata and controls
106 lines (84 loc) ยท 2.87 KB
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
"""
[Problem]
https://leetcode.com/problems/3sum/description/
[Brainstorm]
3 <= nums.length <= 3,000
Brute Force: O(N^3) => 27,000,000,000 => time limited
O(N^2)์ ํ์ด๋ ์๊ฐ ์ ํ์ ๊ฑธ๋ฆฌ์ง ์์ ๊ฒ์ผ๋ก ๋ณด์ธ๋ค. 3,000 * 3,000 => 9,000,000
[Plan]
1. map์ ์ค์ ํ๋ค. key = elements value: index list
2. nested-loop์ ์ํํ๋ค.
2-1. i == j์ธ ๊ฒฝ์ฐ ์ ์ธ
2-2. map์์ ๋์ผํ ์ธ๋ฑ์ค์ธ ๊ฒฝ์ฐ ์ ์ธํ๊ณ ๊ตฌํ๋ค.
"""
from typing import List
class Solution:
"""
Attempt-1 My solution (incorrect)
time limited
"""
def threeSum1(self, nums: List[int]) -> List[List[int]]:
map = {}
for index in range(len(nums)):
values = map.get(nums[index], [])
values.append(index)
map[nums[index]] = values
triplets = set()
for i in range(len(nums)):
for j in range(len(nums)):
if i == j:
continue
complement = -(nums[i] + nums[j])
# print(f"nums[{i}]={nums[i]}, nums[{j}]={nums[j]} , complement={complement}")
if complement in map:
values = map[complement]
for k in values:
if k == i or k == j:
continue
triplets.add(tuple(sorted([nums[i], nums[j], nums[k]])))
return list(triplets)
"""
Attempt-2 Another solution
ref: https://www.algodale.com/problems/3sum/
"""
def threeSum2(self, nums: List[int]) -> List[List[int]]:
triplets = set()
for index in range(len(nums) - 2):
seen = set()
for j in range(index + 1, len(nums)):
complement = -(nums[index] + nums[j])
if complement in seen:
triplet = [nums[index], nums[j], complement]
triplets.add(tuple(sorted(triplet)))
seen.add(nums[j])
return list(triplets)
"""
Attempt-3 Another solution
ref: https://www.algodale.com/problems/3sum/
[Plan]
two-pointer๋ก ์ ๊ทผํ๋ค.
[Complexity]
N: nums.length
Time: O(N^2)
Space: O(1)
"""
def threeSum3(self, nums: List[int]) -> List[List[int]]:
triplets = set()
nums.sort()
for index in range(len(nums) - 2):
left = index + 1
right = len(nums) - 1
while left < right:
three_sum = nums[index] + nums[left] + nums[right]
if three_sum < 0:
left += 1
continue
if three_sum > 0:
right -= 1
continue
triplets.add((nums[index], nums[left], nums[right]))
left += 1
right -= 1
return list(triplets)
sol = Solution()
print(sol.threeSum3([-1, 0, 1, 2, -1, 4]))