📌 문제

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

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

세 수의 합이 0이 되는 값 3개를 반환하라.

📌 아이디어

brute force로는 O(n^3) 이 나올 수 있지만, O(n^2)으로 푸는 것이 목표.

두 가지 풀이법이 있을 수 있다.

1. two pointer 사용
2. i 순회 + 2sum 사용

🔥 2pointer

배열을 정렬하고, i를 순회한다.

for i in range(len(arr)-2):
    if i>0 and arr[i] == arr[i-1]:
        continue
# 중복값 제거

배열이 정렬 돼 있으므로, 세 수의 합인 sum이 0보다 크다면 right --, 0보다 작다면 left ++ 을 해준다.

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

중복된 값이 있을 수 있으므로, 중복된 값을 제거한다.

    while left<right and arr[left] == arr[left+1]:
        left+=1
    while left<right and arr[right] == arr[right-1]:
        right-=1

🔥 i + 2sum 이용