✓[LeetCode] 15. 3Sum

 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.

 

Constraints:

  ▷ 3 <= nums.length <= 3000

  ▷ -105 <= nums[i] <= 105

 

Example:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation: 
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.

 

  3자리 수의 합이 0이 되어야 하니깐.. 한자리씩 뽑아서 맞추면 O(n^3)으로 문제에 주어신 시간을 초과하고 나도 그 방식으로 문제를 풀어 계속 시간 초과로 패스하지 못했다. 답안지를 보면 투 포인트를 이용해 시간을 O(n^2)으로 낮췄다. 다시 한번 포인트 응용을 제대로 하지 못하면 코딩테스트에서 문제가 많이 생길 것이란 걸 깨달았다.

 

1. 우선 숫자가 든 배열을 정렬해준다.

2. 배열의 위치를 하나씩 늘려주면서 좌우 포인트를 설정해 간격을 좁혀가며 모든 경우의 수를 구해준다.

3. 좌우포인트는 현재 위치의 +1과 배열의 마지막이므로 n-2번의 순회를 하면 모든 경우의 수를 다 구할 수 있다.

4. 다음 위치의 값이 전의 값과 같다면 다음 위치로 넘어간다.

5. 같지 않다면 세 수의 값을 더해 0인지 아닌지 확인한다.

6. 합이 0보다 작으면 좌포인트를 한칸 늘려주고, 크면 우포인트를 한칸 줄여준다.

7. 합이 0이라면 좌우포인트를 다른 숫자로 1자리씩 이동시킨다. (그 전에 같은 값이 여러개 일 수 있으니 같은 값의 마지막 위치로 이동시켜준다)

 

 이와 같이 일련의 아이디어를 생각하고 정리하고... 구현할 수 있어야... 이 문제를 스스로 풀 수 있을 것 같다. 이 문제를 난위도 중이므로 최소.. 40분? 안에는 풀어야 할 것 같은데.. 나는 아직도 먼 듯 싶다.. 하지만 꾸준히 풀다보면 익숙해지겠지.. 화이팅!

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        
        results = []
        nums.sort()
        
        for i in range(len(nums) - 2):
            
            # skip the duplicated value
            if i > 0 and nums[i] == nums[i-1]:
                continue
            
            # calculate sum value using 2 points
            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
                
                # sum = 0
                else:
                    results.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 results