1️⃣ 내 풀이 (시간 초과)

두 개 뽑아서 더한 다음 그것에 -1 곱한 수(부호 반대 수)가 있는지 확인

class Solution:
    def threeSum(self, nums: list[int]) -> list[list[int]]:
        answer = set()
        for i in range(len(nums)):
            for j in range(len(nums)):  # 0 ~ len(nums)-1
                if i == j:
                    continue
                sum = nums[i] + nums[j]
                if -sum in nums and nums.index(-sum) not in [i, j]:
                    three = [nums[i], nums[j], -sum]
                    frozen_three = tuple(three)
                    answer.add(frozen_three)

        ans = []  # 🍎
        for item in answer:
            ordered_item = sorted(list(item))
            if ordered_item not in ans:
                ans.append(ordered_item)
        
        return ans

• 시간복잡도를 계산해보자.
  sum in nums ($O(n)$): 파이썬의 list에서 in 연산자는 처음부터 끝까지 값을 하나씩 찾는 선형 탐색을 한다. 리스트의 길이를 $n$이라고 하면 최대 $n$번의 비교가 필요하다.
  nums.index(-sum) ($O(n)$): 이 함수 역시 값이 위치한 인덱스를 찾기 위해 리스트를 처음부터 다시 탐색하므로 $O(n)$이 소요된다.
  그래서 ans = [] # 🍎 의 윗 부분 : O($n^3$)
  
  
  그 아랫 부분도 살펴보자.
  answer의 길이를 $m$이라 하면 $m$만큼 반복되는 반복문을 돌리고 있다.
  한 리스트에 3개씩만 들어있게 고정돼있으므로 정렬을 했을 때 $3log3$ 이므로 여기서 정렬은 $O(1)$이다.
  if ordered_item not in ans:에서 이 in 연산은 $O(ans의 현재 길이)$만큼 걸린다.(최악의 경우 $m-1$) 그니까 $O(m^2)$임을 알 수 있다.
  
  
  더 자세히 말하자면, 총합 계산을 해보았을 때, 루프가 1번째부터 $M$번째까지 도는 동안 핵심이 되는 in 탐색 연산의 횟수는 아래와 같다.
  $0 + 1 + 2 + 3 + \dots + (m-1) = \frac{m(m-1)}{2}$
  이를 빅오 표기법(Big-O)으로 나타내면 고차항만 남으므로 $O(m^2)$이 된다.
  결국 내 풀이의 전체 시간복잡도는 $O(n^3)$이다.

2️⃣ 책 풀이

1. 브루트 포스(시간 초과)

포인터 3개로 겹치지 않게 모든 경우를 검사하면서 함께 중복 배열도 방지하는 것이 똑똑하고 깔끔하다~

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

        for i in range(len(nums) - 2):
            if i > 0 and nums[i] == nums[i-1]: continue  # ‼️
                
            for j in range(i + 1, len(nums) - 1):
                if j > i + 1 and nums[j] == nums[j-1]: continue  # ‼️
                    
                for k in range(j + 1, len(nums)):
                    if k > j + 1 and nums[k] == nums[k-1]: continue  # ‼️
                    if nums[i] + nums[j] + nums[k] == 0:
                        result.append([nums[i], nums[j], nums[k]])

        return result

서로 다른 위치의 세 수를 뽑기 위해 포인터 3개(i, j, k)를 계단식으로 움직인다.

• 정렬을 한 이유
  : 이 알고리즘의 핵심인 중복 제거를 아주 쉽게 만들기 위해서.
  정렬을 해두면 똑같은 숫자들은 [2, 2, 3, 4, 4]처럼 서로 나란히 붙어 있게 되므로, 바로 이전 숫자와만 비교해도 중복을 잡아낼 수 있다.

• ‼️중복 제거 원리
  현재 가리키고 있는 숫자(nums[i])가 바로 직전에 검사했던 숫자(nums[i-1])와 같다면, 어차피 똑같은 숫자의 조합이 만들어지므로 계산하지 않고 continue로 패스(건너뛰기)한다.

• 하지만 3중 반복문을 사용하여 O(n^3)이다. 배열의 크기 범위가 3000이하 이므로 시간 초과.