리트코드 - 세수의 합

https://leetcode.com/problems/3sum/

문제는 해당 링크에서 참고

리스트 안에 있는 값들 중 3개의 요소의 합이 0이 되는 경우를 찾는 문제이다.

완전탐색으로 해결하기에는 시간초과의 리스크가 있는 상황이기 때문에

투포인터 방법으로 해결하였다.

문제해결 Tip

1. 중복된 경우를 제외해야 하기 때문에 중복제외 코드를 생각한다.
2. 투 포인터를 활용하기 쉽게하기 위해 배열을 오름차순 정렬한다.
3. SUM > 0, SUM < 0 을 기준으로 left와 right의 위치를 조절한다.

results = []
nums.sort()

for i in range(len(nums) - 2):  # 3개의 요소를 이용해야하기 때문에 -2 처리

	### 중복인 경우를 제외하기 위한 조건문
	if i > 0 and nums[i] == nums[i-1]:
		continue

반복문에서의 i변수를 세 요소중에 하나로 사용할 것이다.

위 그림 처럼 left와 right는 서로 반대방향에서 시작해서 탐색하게 끔 진행한다.

# left는 i의 한칸 뒤
# right는 배열의 끝에서부터

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

3개의 요소를 인덱싱하기 위한 3개의 변수(i, left, right)가 만들어졌다.

left와 right는 SUM이 0이 되는 것을 찾기위해 변화를 주어야하는데 기준을 SUM > 0,
SUM < 0 인 경우로 한다.

배열이 오름차순 정렬되어있기 때문에 left의 위치가 오른쪽으로 이동할 수록 값이 커질 것이고
right의 위치가 왼쪽으로 이동할 수록 값이 작아질 것이다.

이것을 이용하여

SUM > 0 이면 right의 위치를 -1 이동시키고
SUM < 0 이면 left의 위치를 +1 이동시킬 것이다.
SUM == 0인 경우에는 해당 3개의 요소를 results에 append 해준다.

# right, left가 같아지는 순간에 종료

while left < right: 
	sum = nums[i] + nums[left] + nums[right]
              
	if sum < 0:
    	left += 1
    elif sum > 0:
    	right -= 1
    else:
        results.append([nums[i], nums[left], nums[right]])

	# 중복이 되는 경우를 체크하는 while문
        while left < right and nums[left] == nums[left + 1]:
        	left += 1
                      
        while left < right and nums[right] == nums[right - 1]:
            right -= 1
    
    # 위 과정이 끝나면 left와 right를 한칸씩 움직여서 다음 케이스를 찾게끔 진행한다.
    left += 1
    right -= 1

SUM이 0보다 작기 때문에 left가 1씩 증가되는 모습이다. 최종적으로 맨 마지막 프로세스에서 left가 1 증가되면 right와 같아지게 되서 while문이 종료되고 i가 1증가하게 된다.

SUM이 0이였기 때문에 left와 right가 서로 한칸씩 옮겨왔고 그 순간에도 SUM이 0이고 서로 한칸씩 또 이동하면 while문 조건에 벗어나게 된다.

이러한 방법이 반복되면서 세 수의 합이 0인 경우를 탐색할 수 있다.

*** 전체 CODE ***

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        # 리스트를 오른차순 정렬하여 투포인터를 사용하기 쉽게 한다.
        
        results = []
        nums.sort()

        for i in range(len(nums) - 2):  # 3개의 요소를 이용해야하기 때문에 -2 처리
            # 중복인 경우를 제외하기 위한 조건문
            if i > 0 and nums[i] == nums[i-1]:
                continue

            left = i+1 # left는 i의 한칸 뒤
            right = len(nums) - 1 # right는 배열의 끝에서부터

            while left < right: # 배열의 끝에서부터 시작하는 right가 한칸 씩 앞으로 오면서 left와 같아지는 순간에 종료
                sum = nums[i] + nums[left] + nums[right]
              
                if sum < 0:
                    left += 1
                elif sum > 0:
                    right -= 1
                else:
                    results.append([nums[i], nums[left], nums[right]])

                    while left < right and nums[left] == nums[left + 1]:
                        left += 1
                      
                    while left < right and nums[right] == nums[right - 1]:
                        right -= 1
                    
                    left += 1
                    right -= 1
        return results