[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.

Example 1:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

Example 2:

Input: nums = []
Output: []

Example 3:

Input: nums = [0]
Output: []

Constraints:

0 <= nums.length <= 3000
-105 <= nums[i] <= 105

My Solution

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        # [-4, -1, -1, 0, 1, 2]
        result = []
        for i in range(len(nums)-2):
            left = i+1
            right = len(nums)-1
            if i > 0 and nums[i] == nums[i-1]:
                continue
                
            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

투 포인터를 사용하여 푸는 방법.

1. 정렬을 한다.
2. for loop을 돌면서 num이 나온다.
3. num을 기준으로 바로 뒤에 오는 값이 left가 되고 제일 끝에 있는 값이 right가 된다.
4. num + left + right 값을 구해서 0과 대소 비교를 한다.
5. 0보다 작으면 left를 오른쪽으로 한칸 보낸다. Why? 정렬이 되어있기 때문에 작은 값을 크게 만들어야 0에 가까워지니까.
6. 0보다 크면 right를 왼쪽으로 한칸 보낸다. Why? 정렬이 되어있기 때문에 큰 캆을 작게 만들어야 0에 가까워지니까.

위 과정의 반목을 통해 답을 구할 수 있다!