15. 3Sum

1. Description

• 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.

2. Example

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.

3. Solution

• Runtime: 581ms
• 설명
  • nums리스트를 정렬한다.
  • for문을 사용해 sorted_nums[i]를 첫번째 숫자로 선택한다.
  • if i > 0 and sorted_nums[i] == sorted_nums[i-1]: continue
    • 중복 제거: 이전 숫자와 동일한 숫자가 나오면, 중복된 조합을 방지하기 위해 continue로 건너뛴다.
  • Two-Pointer 알고리즘 적용
    • left포인터는 i+1부터 시작하고, right포인터는 리스트 끝에서 시작한다.
    • 두 개의 포인터를 이동시키면서 sorted_nums[i] + sorted_nums[left]+sorted_nums[right]의 합을 구한다.
  • 세 수의 합이 0인지 확인하고 포인터 이동
    • sum_num이 0보다 작으면, 합을 키우기 위해 left값을 +1하여 증가시킨다.
    • sum_num이 0보다 크면, 합을 줄이기 위해 right값을 -1하여 감소시킨다.
    • sum_num == 0이면 세 개의 수를 result리스트에 추가한다.
  • 중복된 숫자 제거
    • while left < right and sorted_nums[left] == sorted_nums[left - 1]: left += 1
    • left포인터가 가리키는 값이 이전 값과 같으면 left를 증가시켜 중복된 결과가 나오지 않도록 한다.
    • 📌right포인터를 사용하여 중복된 숫자를 제거 가능하다.
      • left += 1: 중복된 작은 수를 건너뛰기 위해 사용
      • right -= 1: 중복된 큰 수를 건너뛰기 위해 사용
      • 둘 다 사용하면 더욱 철저하게 중복을 제거할 수 있다.
      • 기본적으로 left만으로도 대부분의 중복을 처리할 수 있다.

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

4. What I Learned

References

• ChatGPT