리스트 분리(positives, 0, negatives) -> 0이 있는 경우, 없는 경우로 나누어 조합 생성 -> positives, negatives sort해서 BST로 구성 -> (positive, 0, negative)의 경우, O(n) -> (positive, positive, negative)의 경우, hash로 구성해놓고 합을 해가며 찾음 O(k * l) _ k = len(positives), l = len(negatives)
sort하고, 2sum을 구하는 것은 왼쪽, 오른쪽에서 서로 다가오는 방식 -> 정렬 타임만 들어감 O(n l,og n)
class Solution(object):
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
positives = []
negatives = []
zeros = []
for n in nums :
if n > 0 :
positives.append(n)
elif n == 0 :
zeros.append(n)
elif n < 0 :
negatives.append(n)
if len(zeros) != 0 : has_zero = True
sorted_positives = sorted(positives)
sorted_negatives = sorted(negatives)
if has_zero :
나의 풀이
sort하고, 2sum을 구하는 것은 왼쪽, 오른쪽에서 서로 다가오는 방식 -> 정렬 타임만 들어감 O(n l,og n)