3sum

문제

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

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: []

1차 시도:

nested for문 3개 써서 돌렸는데 time limit에서 걸렸다. (for i... for j... for k....)

2차 시도:

풀이 접근방식

1. 정렬(sorted()) 후 리스트 요소를 하나씩 접근한다.
2. 기준을 총 2개 세운다:l, r.
3. 기준에서 +1, -1을 하며 리스트를 순회 ➡️ 합이 0이 되는 요소들을 찾는다.
4. 합이 0인 요소들을 찾았을 경우 이를 result에 추가한다.
5. 중복 요소를 피할 수 있는 코드를 작성한다.
6. 마지막으로 리스트가 순회할 수 있게 l, r 둘 다 하나씩 이동하는 코드를 작성한다.

풀이

def threeSum(nums):
    new_num = sorted(nums)
    length = len(new_num)

    result = []
    
    for i in range(length - 2):
        
        if i > 0 and new_num[i] == new_num[i - 1]:
            continue

        l = i + 1 
        r = length - 1

        while l < r:
            total = new_num[i] + new_num[l] + new_num[r]
            
            if total < 0:
                l += 1

            elif total > 0:
                r -= 1

            elif total == 0:
                result.append([new_num[i], new_num[l], new_num[r]])
                
                while l < r and new_num[l] == new_num[l+1]:
                    l += 1
                    
                while l < r and new_num[r] == new_num[r-1]:
                    r -= 1

                l += 1
                r -= 1

    return result

leetcode discussion에서 찾은 코드.

추가하면 좋은 조건문 :

nums가 모두 0일 경우 ➡️ [0,0,0]을 return 한다.
nums 요소가 3개 이하일 경우 ➡️ 그냥 빈 리스트를 return한다.