[TIL/05.07] Leetcode: 3Sum (Python)

문제

Link

 

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
• -105 <= nums[i] <= 105

풀이

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        result = []

        for x in range(len(nums) - 2):
            # Skip duplicate numbers
            if x > 0 and nums[x] == nums[x-1]: 
                continue

            y, z = x+1, len(nums)-1


            while y < z:
                sum = 0 - nums[x]
            
                if y < z and nums[y] + nums[z] == sum:
                    result.append([nums[x], nums[y], nums[z]])
                    
                    # Skip duplicate numbers
                    while y < z and nums[y] == nums[y+1]:
                        y += 1
                    while y < z and nums[z] == nums[z-1]:
                        z -= 1
                    
                    y += 1
                    z -= 1
                
                elif nums[y] + nums[z] < sum:
                    y += 1
                else:
                    z -= 1

        return result

배운 내용

✏️ 배움 기록

• 리스트에 요소들을 리스트로 묶어서 추가하기 

result.append(list([nums[x], nums[y], nums[z]]))

• x는 전체 for문으로 증가시키기 + 중복 처리하기 

• y,z의 중복 효율적으로 처리하기

while y < z and nums[y] == nums[y+1]:
    y += 1
while y < z and nums[z] == nums[z-1]:
    z -= 1

 

➤ 중복된 조합을 건너뛰기 위해 현재의 y와 z가 가리키는 숫자가 다음 숫자와 이전 숫자와 같은지를 확인하고, 같으면 y와 z를 각각 증가 혹은 감소시켜서 중복된 조합을 건너뛰게 함 

 

• y,z의 타겟값 처리하기

• nums[y] + nums[z] < sum: y와 z가 가리키는 숫자의 합이 타겟값보다 작으면, 작은 수 쪽의 포인터(y)를 오른쪽으로 이동시켜 더 큰 값을 만나도록 함
• nums[y] + nums[z] > sum: y와 z가 가리키는 숫자의 합이 타겟값보다 크면, 큰 수 쪽의 포인터(z)를 왼쪽으로 이동시켜 더 작은 값을 만나도록 함