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.

주어진 정수 배열에 대해서 세 원소를 뽑아 triplet을 만들때, 각 원소의 합이 0이 되는 쌍들을 구해
배열로 만들어 리턴하시오

중복된 triplet은 있어선 안됩니다.

예시

Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.

제한

• $3 <= nums.length <= 3000$
• $-10^5 <= nums[i] <= 10^5$

풀이

1. 먼저 주어진 배열을 오름차순으로 정렬한다.
2. 오름 차순으로 정렬한 배열을 0 ~ 배열의 길이 - 3 의 범위의 index로 loop 한다.
   2-1.loop의 안에는 left와 right를 두어 left는 2번 loop값 + 1, right는 배열의 크기 - 1이 되도록 한다.
   2-2.2번 loop index, left, right 에 각각 해당하는 index의 값을 더해 0인지 확인후 0이면 답에 추가한다.
   2-3a.만약 0보다 작으면 left 증가한다, 배열이 오름차순 정렬되어있기에, left를 증가하면 값이 증가한다.
   하지만, left를 증가해도 값이 같으면 중복 triplet이 생길수 있기에 더 증가시킨다.
   2-3b. 0보다 크면 right를 감소한다.
   2-4. left < right 가 지켜지지 않으면 loop 종료
3. index를 1 증가한다, 만약에 증가한 index에 대해 값이 바뀌지 않으면 값을 더 증가한다.

코드

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        ans = []
        for target in range(0, len(nums)-2):
            if target != 0 and nums[target-1] == nums[target]: continue
            left = target + 1
            right = len(nums) - 1
            while left < right and right > target:
                if nums[target] + nums[left] + nums[right] == 0:
                    ans.append([nums[target], nums[left], nums[right]])
                    while left != len(nums)-1 and nums[left + 1] == nums[left]: left += 1
                    left += 1
                    while right != target+1 and nums[right - 1] == nums[right]: right -= 1
                    right -= 1
                elif nums[target] + nums[left] + nums[right] < 0:
                    while left != len(nums)-1 and nums[left + 1] == nums[left]: left += 1
                    left += 1
                else:
                    while right != target+1 and nums[right - 1] == nums[right]: right -= 1
                    right -= 1
        return ans