15. 3Sum ★

15. 3Sum

 

첫 번째 내코드 

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

        nums.sort()
        for l in range(len(nums)):
            if l > 0 and nums[l] == nums[l - 1]:
                continue
            m, r = l+1, len(nums)-1

            while m<r:
                sub_sub = nums[m] + nums[r] + nums[l]
                if sub_sub == 0:
                    res.append([nums[l], nums[m], nums[r]])

                    # 중복 제거: 동일한 m, r 값 건너뛰기
                    while m < r and nums[m] == nums[m + 1]:
                        m += 1
                    while m < r and nums[r] == nums[r - 1]:
                        r -= 1

                    r-= 1
                    m+=1
                elif sub_sub > 0:
                    r -=1
                else:
                    m +=1

        return res

 

 

• l > 0:
  • 첫 번째 요소(l = 0)는 이전 값이 없으므로 비교할 필요가 없습니다.
  • l > 0 조건이 없으면 nums[l - 1]에서 인덱스 오류가 발생할 수 있습니다.
• nums[l] == nums[l - 1]:
  • 현재 값이 이전 값과 동일하면 중복된 값을 처리하기 위해 현재 반복을 건너뜁니다.
  • 이렇게 하면 동일한 조합이 결과에 추가되지 않습니다.

 

 

https://youtu.be/jzZsG8n2R9A?si=9ZYksLSSfhuBfkpL

 

https://youtu.be/1BGiX1ZZUpQ?si=PGqVtJh21ErxdO3c

 

최종 코드

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        # 결과를 저장할 리스트
        res = []

        # nums 배열을 정렬하여, 투 포인터 알고리즘을 사용할 수 있도록 함
        nums.sort()

        # 배열의 각 원소를 기준으로 순회
        for i, a in enumerate(nums):
            # i가 0보다 클 때, 현재 값이 이전 값과 같다면 중복된 조합이 되므로 건너뜀
            if i > 0 and a == nums[i - 1]:
                continue

            # 왼쪽 포인터는 현재 위치 바로 다음, 오른쪽 포인터는 맨 끝에서 시작
            l, r = i + 1, len(nums) - 1

            # 두 포인터가 교차하기 전까지 반복
            while l < r:
                # 현재 세 수의 합 계산
                threeSum = a + nums[l] + nums[r]

                # 합이 0보다 크면, 숫자를 줄이기 위해 오른쪽 포인터를 왼쪽으로 이동
                if threeSum > 0:
                    r -= 1
                # 합이 0보다 작으면, 숫자를 키우기 위해 왼쪽 포인터를 오른쪽으로 이동
                elif threeSum < 0:
                    l += 1
                # 합이 0이면, 유효한 세 수의 조합이므로 결과 리스트에 추가
                else:
                    res.append([a, nums[l], nums[r]])

                    # 다음 조합을 찾기 위해 왼쪽 포인터 이동
                    l += 1

                    # 중복된 값은 스킵 (같은 값을 여러 번 추가하지 않기 위해)
                    while l < r and nums[l] == nums[l - 1]:
                        l += 1

        # 결과 리스트 반환
        return res

 

이 알고리즘은 정렬된 배열을 기반으로

각 숫자에 대해 양 끝에서 투 포인터를 이동시키며 합이 0이 되는 조합을 찾는 방식입니다.
중복 방지를 위해 기준 숫자(a)와 왼쪽 포인터(l)의 값을 비교하여 같은 값이 연속될 경우 건너뛰는 로직이 핵심입니다.