[Python] List <세 수의 합>

포인터를 정해놓고 리스트 인덱스를 옮겨가며, 연산 후 비교하는 로직을 구성하면 쉽게 풀 수 있으나, 문제는 세 수의 합이기 때문에 자칫 삼중 for문을 사용하는 불상사가 발생할 수 도 있다. 

이 문제 역시 두 개의 포인터를 사용하여 쉽게 풀이가 가능하다.

---

1 씩 증가하는 리스트 인덱스 i를 만들어 놓은 뒤, i 뒤쪽의 나머지 배열의 양 끝을 left와 right로 나눈다. 

이때, i, left, right 위치의 값들을 더하여 0과 비교하고, 0보다 작다면 right를 감소, 크다면 left를 증가시키는 방식으로 풀이할 수 있다.

 

from typing import List


def sum_of_three(nums_list: List[int]) -> List[List[int]]:
    nums_list.sort()
    result = []
    for i in range(len(nums_list)-2):
		
        # 중복 인자는 바로 스킵할 수 있도록
        if i > 0 and nums_list[i] == nums_list[i-1]:
            continue

        left = i + 1
        right = len(nums_list) - 1

        while left < right:
            sums = nums_list[i] + nums_list[left] + nums_list[right]
            if sums < 0:
                left += 1
            elif sums > 0:
                right -= 1
            else:
                sub = [nums[i], nums_list[left], nums_list[right]]
                result.append(sub)
				
                # 중복 인자가 나올 시 바로 스킵
                while left < right and nums_list[left] == nums_list[left + 1]:
                    left += 1
                while left < right and nums_list[right] == nums_list[right - 1]:
                    right -= 1
				
                # while문이 계속 돌 수 있게 다음 인자로
                right -= 1
                left += 1

    return result


if __name__ == '__main__':
    nums = [-1, 0, 1, 2, -1, -4]
    print(sum_of_three(nums))