Intuition

1차원 리스트에서 세 원소의 합이 0이 되는 원소들을 출력
출력되는 원소의 순서는 상관 없으나 중복되는 원소가 있을 수 있으며 중복되는 정답은 하나만 적어야 함

Approach

• for문을 통해 세 원소 중 하나의 원소를 정의하면, 두개의 원소의 합을 구하는 문제로 바뀜.
• 원소의 순서는 상관 없으므로 sort를 사용
• 중복되는 값이 존재하여 for문 순회하거나 투포인터 이동과정에서 중복을 검사하는 코드가 필요.-> 중복을 검사하더라도 조건(s)은 만족해야 함

Complexity

• Time complexity: $O(n^2)$
  • for문으로 첫번째 원소 정의 n x 두 원소의 합 확인 n
• Space complexity: $O(n)$

Code

class Solution:

    def threeSum(self, nums: List[int]) -> List[List[int]]:
        sorted_nums = sorted(nums)
        answer = []
        for i in range(len(sorted_nums)-2):
            target = 0 - sorted_nums[i]
            s = i+1
            e = len(sorted_nums)-1
            if i > 0 and sorted_nums[i] == sorted_nums[i-1]: continue

            while s<e:
                sum = sorted_nums[s] + sorted_nums[e]
                if sum < target:
                    s += 1
                elif sum > target:
                    e -= 1
                else:
                    answer.append([sorted_nums[i], sorted_nums[s], sorted_nums[e]])
                    while s < e and sorted_nums[s] == sorted_nums[s+1]: s += 1
                    while s < e and sorted_nums[e] == sorted_nums[e-1]: e -= 1

                    s += 1
                    e -= 1
        
        return answer