forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathKwonNayeon.py
More file actions
63 lines (52 loc) ยท 2.03 KB
/
KwonNayeon.py
File metadata and controls
63 lines (52 loc) ยท 2.03 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
"""
Constraints:
1. 3 <= nums.length <= 3000
2. -10^5 <= nums[i] <= 10^5
Time Complexity: O(n^2)
- ์ ๋ ฌ์ O(n log n), ์ด์ค ๋ฐ๋ณต๋ฌธ์ O(n^2)
Space Complexity: O(n)
- ๊ฒฐ๊ณผ ๋ฆฌ์คํธ๋ฅผ ์ ์ฅํ๋ ๋ฐ ํ์ํ ๊ณต๊ฐ
ํ์ด ๋ฐฉ๋ฒ:
- ํฌ ํฌ์ธํฐ๋ฅผ ํ์ฉํ์ฌ ํฉ์ด 0์ด ๋๋ ์ธ ์ ์กฐํฉ ์ฐพ๊ธฐ
- ๋ฐฐ์ด ์ ๋ ฌ: ํฌ ํฌ์ธํฐ ์ฌ์ฉ + ์ค๋ณต ์ฒ๋ฆฌ ์ฉ์ด
- for ๋ฃจํ: ์ฒซ ๋ฒ์งธ ์ซ์ ์ ํ (len(nums)-2๊น์ง)
- ์ค๋ณต๋ ์ฒซ ๋ฒ์งธ ์ซ์ ๊ฑด๋๋ฐ๊ธฐ
- left, right ํฌ์ธํฐ ์ค์
- while ๋ฃจํ: ๋ ํฌ์ธํฐ๊ฐ ๊ต์ฐจํ์ง ์์์ผ ํจ
- sum = nums[i] + nums[left] + nums[right] ๊ณ์ฐ
- sum == 0: ๊ฒฐ๊ณผ ์ถ๊ฐ, ์ค๋ณต ๊ฑด๋๋ฐ๊ธฐ, ์์ชฝ ํฌ์ธํฐ ์ด๋
- sum < 0: left ์ฆ๊ฐ (๋ ํฐ ๊ฐ ํ์)
- sum > 0: right ๊ฐ์ (๋ ์์ ๊ฐ ํ์)
- ์ต์ข
๊ฒฐ๊ณผ ๋ฐํ
"""
# Brute-force: three nested loops โ O(n^3)
# Optimized: sort + two pointer โ O(n^2)
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
# Step 1: Sort the array
# Step 2: Fix one number using for loop
# Step 3: Use two pointers to find two other numbers
# - if sum == 0: valid triplet
# - if sum < 0: move left pointer
# - if sum > 0: move right pointer
nums.sort()
result = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i-1]:
continue
left, right = i+1, len(nums)-1
while left < right:
sum = nums[i] + nums[left] + nums[right]
if sum == 0:
result.append([nums[i], nums[left], nums[right]])
while left < right and nums[left] == nums[left+1]:
left += 1
while left < right and nums[right] == nums[right-1]:
right -= 1
left += 1
right -= 1
elif sum < 0:
left += 1
else:
right -= 1
return result