[leetcode] 3Sum

3Sum

생각한 방식

• 3중 for문으로 접근
  ⇢ 시간초과
• combination 사용
  ⇢ 시간초과

풀잇법

처음 combination을 떠올리면서 nums를 정렬해야 하나 고민했다.

합쳐서 0이 되는 경우 중 하나이다. 왼쪽에 있는 -1에서 0이 되는 값 [-1, 0, 1]을 찾았기 때문에 오른쪽에 있는 -1일 때 [0, 1, -1]는 굳이 확인할 필요 없다.

정렬하면 두 번 이상 계산하는 일을 막을 수 있다.

-1로 시작한 적이 있다면 다시 계산하지 않아도 된다.

위 사진에서 대략 알 수 있듯이, 세 개의 화살표가 가리킨 값의 합이 0이 되는지 확인하면 된다.

이 다음에는 빨간색 화살표가 어디로 가야 할까? 0으로 가야 한다. 여기서는 양수밖에 없어서 답이 나올 수 없다.

코드

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:result = []
        nums = sorted(nums)
        
        for i in range(len(nums)-2):
            if i > 0 and nums[i] == nums[i-1]:
                continue
                
            start, end = i+1, len(nums)-1
            while start < end:
                sum3 = nums[i] + nums[start] + nums[end]
                if sum3 == 0:
                    result.append([nums[i], nums[start], nums[end]])
                    
                    start += 1
                    while nums[start] == nums[start-1] and start < end:
                        start += 1
                        
                    end -= 1
                    while nums[end] == nums[end+1] and start < end:
                        end -= 1
                    
                    
                elif sum3 > 0:
                    end -= 1
                else:
                    start += 1
        
        return result

참고 자료

NeetCode's Youtube