forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathaa601.py
More file actions
27 lines (26 loc) ยท 917 Bytes
/
aa601.py
File metadata and controls
27 lines (26 loc) ยท 917 Bytes
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
# ์ ์ฒด ์๊ฐ๋ณต์ก๋ : O(n^2), ๊ณต๊ฐ๋ณต์ก๋ : O(n)
class Solution:
def threeSum(self, nums: list[int]) -> list[list[int]]:
nums.sort() # ๋ด์ฅํจ์ sort()์ ์๊ฐ๋ณต์ก๋ O(nlogn)
result = [] # ๊ณต๊ฐ๋ณต์ก๋ O(n)
# ์๊ฐ๋ณต์ก๋ O(n)
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i - 1]:
continue
r = len(nums) - 1
l = i + 1
# i๋ฅผ ๊ธฐ์ค์ผ๋ก l๊ณผ r์ ํ์ํ๋ ์๊ฐ ๋ณต์ก๋ : O(n)
while l < r:
if nums[i] + nums[l] + nums[r] < 0:
l += 1
elif nums[i] + nums[l] + nums[r] > 0:
r -= 1
else:
result.append([nums[i], nums[l], nums[r]])
while l < r and nums[l] == nums[l + 1]: # ์ค๋ณต ์ ๊ฑฐ ๋ฐ๋ณต๋ฌธ, ์ด๋ฏธ ์งํ๋ ๋ฆฌ์คํธ๋ฅผ ๋ค์ ํ์ํ์ง ์์ผ๋ฏ๋ก ์๊ฐ๋ณต์ก๋๋ ์ถ๊ฐ๋์ง ์์
l += 1
while l < r and nums[r] == nums[r - 1]:
r -= 1
l += 1
r -= 1
return result