투 포인터를 활용한 문제입니다.

문제

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

제한사항

• 0 <= nums.length <= 3000
• $10^5$ <= nums[i] <= $10^5$

접근

주어진 배열 내 3개의 원소의 합이 0인 Triplet 목록을 반환해야 해요. 대신 전제 조건이,

1. 같은 인덱스의 원소끼리 있으면 안된다.
2. Triplet 원소가 중복되면 안된다.

입니다. 먼저 인덱스 중복을 막기 위해 아래와 같은 로직을 전개했습니다.

1. 기준 인덱스를 잡음(0부터 배열 길이 - 2까지)
2. 좌측 인덱스기준 + 1와 우측 인덱스마지막 인덱스부터 시작해서 합이 0임을 확인
   2-1. 합이 0일 경우, 좌측 인덱스를 증가, 우측 인덱스를 감소
   2-2. 합이 0보다 클 경우, 우측 인덱스를 감소
   2-3. 합이 0보다 클 경우, 좌측 인덱스를 감소
3. 좌측 인덱스와 우측 인덱스가 같기 전까지 전개하고, 완료되면 기준 인덱스를 증가

해당 로직을 수행하려면 전제 조건이 배열이 오름차순 정렬이 되어야 합니다. 그래서 전개 전에 정렬을 수행해야 해요. 참, 정답을 포함하기 전에 해당 배열 원소 리스트에 대한 중복 예외 처리도 해줘야 해요.

답안

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> answer = new ArrayList<>();
        if(nums.length < 3)
            return answer;

        Arrays.sort(nums);
        for(int i = 0; i < nums.length - 2; ++i){
            int nLeft = i + 1;
            int nRight = nums.length - 1;
            while(nLeft < nRight){
                List<Integer> values = new ArrayList<>();
                {
                    values.add(nums[i]);
                    values.add(nums[nLeft]);
                    values.add(nums[nRight]);
                }
                int nCandidate = values.get(0) + values.get(1) +values.get(2);
                if(nCandidate == 0){
                    if(!answer.contains(values))
                        answer.add(values);
                    ++nLeft; --nRight;
                }
                else if(nCandidate < 0){
                    ++nLeft;
                }
                else{
                    --nRight;
                }
            }
        }

        return answer;
    }
}