[파이썬 알고리즘 인터뷰] 3수의 합

3Sum - LeetCode

브루트포스로 계산

def threeSum(self, nums: List[int]) -> List[List[int]]:
    results=[]
    nums.sort()

    for i in range(len(nums)-2):
        if i>0 and nums[i]==nums[i-1]:
            continue
        for j in range(i+1,len(nums)-1):
            if j>i+1 and nums[j]==nums[j-1]:
                continue

            for k in range(j+1,len(nums)):
                if k>j+1 and nums[k]==nums[k-1]:
                    continue
                if nums[i]+nums[j]+nums[k]==0:
                    results.append([nums[i],nums[j],nums[k]])
    return results

가장 기본적인 방법인 브루트포스로 시도해보니 역시나 O(n³)으로 타임오버가 나왔다.

투 포인터로 합 계산

def threeSum(self, nums: List[int]) -> List[List[int]]:
        result=[]
        nums.sort()
        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:
                    left +=1
                elif sum>0:
                    right-=1
                else:
                    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
        return result

 

투포인터를 이용하여 O(n²)로 처리하였다. 

 

기본적인 쉬운 문제인데 확실히 아직 파이썬 문법에 익숙해지지 않아서 그런지 이런 단순한 문제에서 더 헤매는 것 같다... 이런건 빠르게 후딱 끝내야하는데,,, 역시나 연습만이 답인 것 같다....