[LeetCode]15. 3Sum - Python 문제 풀이

문제

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

nums라는 array가 주어졌을 때 3개의 인덱스값은 모두 다르고, 각각의 합이 0인 3개의 값 조합을 return 하시오.

 

풀이

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        '''
        left = 0
        right = 1
        '''
        ans = []

        # two pointer 문제로 풀기 위하여 sort를 해줘야 한다.
        nums = sorted(nums) 

        # 이 아래 조건문은 모두 테스트 케이스의 예외를 처리하기 위함 !
        if len(nums) == 3 and sum(nums) != 0:
            return []
        if nums == [0,0,0]:
            return [[0,0,0]]

        # 이번 투포인터는 하나의 값을 미리 고정시키고
        # 나머지의 값들 중에서 투포인터를 적용 !
        for i in range(len(nums)):
            # 고정된 값 
            # 각각의 값을 기준으로 더했을 때 0이 되는 조건을 만족하는 모든 경우의 수를 볼 것임
            fix = nums[i]

            # fix 와 겹치지 않기 위해
            # fix의 인덱스 다음의 인덱스를 하나의 포인터로 지정
            # 또 다른 하나의 포인터는 맨끝에 위치시킴
            left = i+1
            right = len(nums) - 1 

            # 중복을 제거하기 위해 이전 값과 같을 경우는 생략 !
            # 이 모든게 정렬을 했기 때문에 가능 
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            
            # 하나의 값을 고정하고 투포인터 시작
            while left < right :
                
                # a 는 투포인터의 합
                a = nums[left] + nums[right]

                # 만약 투포인터의 값과 고정값의 합이 0일 경우 답을 추가 
                if fix + a == 0:
                    candid = [nums[left], fix, nums[right]]
                    # ans 내의 중복을 없애기 위하여 
                    if candid not in ans:
                        ans.append(candid)
                    # 만약에 답을 추가를 하고 난 뒤에도 left가 움직이지 않는다면
                    # 다른 경우를 볼 수 없음 
                    # 그렇기 때문에 답을 추가하고 난 뒤에도 움직여야 함 **중요**
                    left += 1
                
                # 만약 3개의 값의 합이 0보다 작을 경우 숫자가 부족한 것이기 때문에 
                # 더 큰값으로 left를 움직임
                elif fix + a < 0:
                    left += 1
                # 합이 너무 클 경우에는 값을 줄여줌
                else: 
                    right -= 1
        
        return ans

• 시간 복잡도 : O(NlogN)
  • 보통 투 포인터로 풀게 된다면 --> O(logN)
  • 근데 이 문제는 투포인터를 nums의 길이만큼 반복하기 때문에 --> O(NlogN)