리트코드 - 3Sum

문제

https://leetcode.com/explore/interview/card/top-interview-questions-medium/103/array-and-strings/776/

문제 설명

정수 배열 nums가 주어질 때, 다음 조건을 만족하는 모든 세 숫자 조합 [nums[i], nums[j], nums[k]]을 반환하세요

• i != j, i != k, j != k (즉, 세 숫자의 인덱스가 모두 달라야 합니다.)
• nums[i] + nums[j] + nums[k] = 0 (세 숫자의 합이 0이어야 합니다.)

주의: 결과 집합에는 중복된 세 숫자 조합이 포함되지 않아야 합니다.

---

예제

예제 1:

• 입력: nums = [-1, 0, 1, 2, -1, -4]
• 출력: [[-1, -1, 2], [-1, 0, 1]]
• 설명:
  • ( 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 )
  • 중복되지 않은 조합은 [-1, -1, 2]와 [-1, 0, 1]입니다.
  • 출력의 순서는 중요하지 않습니다.

예제 2:

• 입력: nums = [0, 1, 1]
• 출력: []
• 설명: 가능한 모든 세 숫자의 조합이 0이 되지 않습니다.

예제 3:

• 입력: nums = [0, 0, 0]
• 출력: [[0, 0, 0]]
• 설명: ( nums[0] + nums[1] + nums[2] = 0 + 0 + 0 = 0 ).

---

풀이

해당 문제는 투 포인터를 활용하여 문제를 해결할 수 있습니다. 문제 해결 순서는 다음과 같습니다.

1. 배열 정렬

• 배열을 오름차순으로 정렬합니다. 이렇게 하면 중복된 결과를 쉽게 제거하고 투 포인터를 효율적으로 활용 할 수 있습니다.

2. 반복문 + 투 포인터

• 배열을 순회하면서 각 원소를 기준으로 나머지 두 원소를 찾아 세 숫자의 합이 0 이 되는 조합을 찾습니다.

3. 중복 제거

• 정렬 된 상태에서 각 숫자가 반복되지 않도록 이전 숫자와 같으면 배열 순회를 생략합니다.

 

코드

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

        for i in range(N-2):
            left, right = i+1, N -1

            # 중복되는 triplets 제외
            if i > 0 and nums[i] == nums[i-1]:
                continue

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

                if target == 0:
                    answer.append([nums[i], nums[left], nums[right]])

                    # 중복제거
                    while left<right and (nums[left] == nums[left+1]):
                        left += 1

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

                    left += 1
                    right -= 1

                elif target <0 :
                    left +=1 
                else :
                    right -=1

        return answer