three sum

# 임의의 숫자 배열이 있음

# nums = [-1, 0, 1, 2, -1, -4]

# nums 에서 임의의 3 숫자를 더해서 0이 나오는 숫자들을 별도로 모은 배열을 리턴해야 함

# [[-1, -1, 2], [-1, 0, 1]]

# x+y+z = 0 이 되어야 한다고 가정한다면

# x, y, z 각각 반복문의 index 를 변화시키면서 더하고 0 이 나왔을 때만 결과 배열에 append 하면 될 것 같음

# 근데 투 포인터를 사용하면 시간복잡도를 줄일 수 있을 것 같음

# x 값은 왼쪽에서 오른쪽으로 이동하고
# y 값은 왼쪽에서 오른쪽
# z 값은 오른쪽에서 왼쪽으로 이동하면서 합을 구해보면 될 것 같음

# nums 를 정렬한 다음 합이 0보다 작거나 클때 y, z index 를 이동시키면 0 을 쉽게 맞출 수 있을 것 같음

# 전체 반복문은 y, z 를 고려하여 전체길이에서 2를 뺀만큼만 x index 가 변화하도록 함

# x 값이 직전 x 값과 같으면 반복문을 수행하지 않음
# y 값이 직전 y 값과 같으면 반복문을 수행하지 않음
# z 값이 직전 z 값과 같으면 반복문을 수행하지 않음

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

        result = []
        sorted_nums = sorted(nums)

        for x_index in range(len(sorted_nums)-2):

            y_index = x_index+1
            z_index = len(sorted_nums)-1
            if x_index > 0 and sorted_nums[x_index] == sorted_nums[x_index-1]:
                continue

            while y_index < z_index:

                total_sum = sorted_nums[x_index] + \
                    sorted_nums[y_index]+sorted_nums[z_index]

                if total_sum == 0:

                    result.append(
                        [sorted_nums[x_index], sorted_nums[y_index], sorted_nums[z_index]])

                    while y_index < z_index and sorted_nums[y_index] == sorted_nums[y_index+1]:

                        y_index += 1

                    while y_index < z_index and sorted_nums[z_index] == sorted_nums[z_index-1]:

                        z_index -= 1

                    y_index += 1
                    z_index -= 1

                elif total_sum > 0:

                    z_index -= 1

                elif total_sum < 0:

                    y_index += 1

        return result