Initial Solution
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
res = []
n = len(nums)
seen = {}
for i in range(n):
a = i + 1
b = n - 1
num1 = nums[i]
target = 0 - num1
for _ in range(i + 1, n):
if a >= b:
break
num2 = nums[a]
num3 = nums[b]
if target > num2 + num3:
a += 1
elif target < num2 + num3:
b -= 1
else:
res.append([num1, num2, num3])
a += 1
res = list(set([tuple(r) for r in res]))
return res
Python
복사
Time complexity and Space Complexity
Time: O(n²) - sorting takes O(n log n), and the outer loop runs n times with inner two-pointer scan taking O(n), resulting in O(n²) overall.
Space: O(n) - using a set to store tuples for deduplication, which in worst case could store O(n²) triplets.
What I didn’t know
•
Cannot pass the last test case
→ many zeros only
Other Better Solutions
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
n = len(nums)
res = []
for i in range(n - 2):
if i > 0 and nums[i] == nums[i - 1]:
continue # 1) i 중복 스킵
a, b = i + 1, n - 1
target = -nums[i]
while a < b: # 3) while 루프
s = nums[a] + nums[b]
if s < target:
a += 1
elif s > target:
b -= 1
else:
res.append([nums[i], nums[a], nums[b]])
a += 1
b -= 1 # 2) 둘 다 이동
# 2) a/b 중복 스킵
while a < b and nums[a] == nums[a - 1]:
a += 1
while a < b and nums[b] == nums[b + 1]:
b -= 1
return res
Python
복사
Time complexity and Space Complexity
Time: O(n²) - sorting takes O(n log n), and the outer loop runs n times with inner two-pointer scan taking O(n), resulting in O(n²) overall.
Space: O(1) - only using constant extra space for pointers and variables, excluding the output array.