해당 풀이는 파이썬 알고리즘 인터뷰 책을 참고하였습니다.

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.

• 투포인터란?
  • 왼쪽과 오른쪽에 각각 포인터를 하나씩 두고 포인터가 가리키는 수의 합이 타겟과 맞는 지 확인하고, (각 포인터가 겹치지 않는 조건 하에)타겟되는 수보다 작다면 왼쪽 포인터를 +1, 크다면 오르쪽 포인터를 -1 해서 타겟까지 오는 방법이다.
• 해당 문제를 투포인터를 이용해 풀 수 있었던 이유는 리트코드의 Two-Sum 문제와 달리 배열의 인덱스가 아닌 값을 찾아내는 문제라 가능했다. 기본적으로 투포인터를 사용하려면 배열의 정렬이 필요한데 정렬해버리면 인덱스도 엉망이 되어버린다.

public List<List<Integer>> threeSum2(int[] nums) {
    List<List<Integer>> list = new ArrayList<>();
    Arrays.sort(nums);
    int left, right, sum;

    for (int i = 0; i < nums.length - 2; i++) {
        // 중복값 건너뛰기
        if (i > 0 && nums[i] == nums[i - 1]) continue;

        // i를 기준으로 left는 i 바로 왼쪽부터, right는 배열의 끝부터
        left = i + 1;
        right = nums.length - 1;

        // 배열의 세 자리의 합을 구해서 0이 나오는 지 확인. left는 right를 넘어갈 수 없다.
        while (left < right) {
            sum = nums[i] + nums[left] + nums[right];
            if (sum < 0) {
                left += 1;
            } else if (sum > 0) {
                right -= 1;
            } else {
                list.add(Arrays.asList(nums[i], nums[left], nums[right]));

                // 중복된 값을 피하기 위해 left가 right를 넘어가지 않는 조건 하에 앞 자리와 같은 수가 있으면 스킵
                while (left < right && nums[left] == nums[left + 1]) {
                    left++;
                }
                while (left < right && nums[right] == nums[right - 1]) {
                    right--;
                }

                // 마지막으로 한 칸씩 더 옮겨 온다(마찬가지로 중복값을 피하기 위해).
                left++;
                right--;
            }
        }
    }

    return list;
}

ㅋㅋ3sum