[Leetcode] 15. 3Sum

문제

 

https://leetcode.com/problems/3sum/

3Sum - LeetCode

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	Output
nums = [-1,0,1,2,-1,-4]	[[-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	Output
nums = [0,1,1]	[]
Explanation: The only possible triplet does not sum up to 0.

 

 

문제풀이 코드

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        result = set()
        for i in range(len(nums) - 2):
            if i > 0 and nums[i-1] == nums[i]:
                continue
            j = i + 1
            k = len(nums) - 1
            while j < k:
                if nums[i] + nums[j] + nums[k] > 0:
                    k -= 1
                elif nums[i] + nums[j] + nums[k] < 0:
                    j += 1
                else:
                    result.add((nums[i],nums[j],nums[k]))
                    while j < k and nums[j] == nums[j+1]:
                        j+=1
                    while j < k and nums[k] == nums[k-1]:
                        k-=1
                    j += 1
                    k -= 1
        return [list(x) for x in result]

투포인터 방식으로 문제접근

 

1. 투포인터를 사용하기위해 nums를 오름차순으로 정렬해준다

2. 반복문을 돌면서 i,j 또는 k를 조건에 맞게 계산해준다.

  (1). i값이 0보다 크고 현재 값이 이전값과 동일하면 continue를 해준다(안해주면 이전과 같은 일을 반복해서 느려짐)

  (2). nums[i] + nums[j] + nums[k] > 0일 때는 합을 줄여줘야하기 때문에 k = k-1을 해준다

  (3). nums[i] + nums[j] + nums[k] < 0일 때는 합을 키워야하기 때문에 j = j+1을 해준다

  (4). nums[i] + nums[j] + nums[k] == 0일 때 세개의 수를 집합에 담아준다(중복을 피하기위함)

        - 현재의 값과 그다음값 또는 현재의 값과 그 이전값이 동일할 수 있어 현재와 다른 값이 나올 때 까지 j=j+1, k=k-1

          을 해준다(없어도 통과는 되지만 시간복잡도가 마지막에 겨우 걸쳐짐)