LeetCode: 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]]
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.

Example 2:

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

Example 3:

Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.

 

Constraints:

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

 

 

이 문제는 두 개의 포인터를 써서 풀어야 하는 문제이다. 

 

처음에 봤을때는 부르트포스를 사용하여 풀어야하나 싶었지만 보나마나 시간초과가 뜰 것 같아 다른 방식을

찾아보았다. 

 

일단 받은 행렬인 nums를 정렬한 후 for문에서 탐색한다. 

 

탐색을 하는데 이전의 숫자와 같은 경우 중복이 되면 안되기 때문에 if문을 사용해서 중복제거를 한다. 

 

이후 현재위치 i와 left right를 더한 값을 비교하여 0보다 적으면 left를 한칸 위로

0보다 크면 right를 한칸 아래로 움직인다. 

 

만약 total이 0 이라면 결과값 추가 후에 숫자 중복이 되지 않게 while문을 사용하여 중복된 숫자를 검사한다. 

 

 

 

---

구현코드

 

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        nums.sort()
        res = []

        for i in range(len(nums)):
            if i>0 and nums[i] == nums[i-1]:
                continue
            
            left = i+1
            right = len(nums)-1

            while left < right:
                total = nums[i] + nums[left] + nums[right]

                if total <0:
                    left += 1
                elif total > 0:
                    right -= 1
                else:    
                    res.append([nums[i], nums[left], nums[right]])

                    while left<right and nums[left] == nums[left+1]:
                        left += 1
                    while left<right and nums[right-1] == nums[right]:
                        right -= 1

                    left += 1
                    right -= 1

        return res