(Array, Medium) 3Sum

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

Medium 문제기 때문에 당연히 O(n^3)으로는 하지 않는 것을 생각한다.
i, j, k가 있을 때 j+k 합산과 i를 더했을 때 0이면 타켓이라고 볼 수 있긴 하다.

그럼 일단 O(n^2)까지는 가능할 것 같다.
맵에 i에 대한 value, index를 세팅해놓고 이중 for문으로 합산만들어서 계산해본다.

j+k로 키에 접근 가능해야 하기 때문에 맵의 키는 nums[i]가 되고,
map으로 부터 조회할 때는 0 - (j+k) 해서 차액이 맵에 있는지 조사하면 되겠다.

import java.util.*;
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {

        // value, index map
        Map<Integer, Integer> map = new HashMap<>();
        for (int i=0; i<nums.length; i++) {
            map.put(nums[i], i);
        }

        Set<List<Integer>> answerSet = new HashSet<>();

        for (int j=0; j<nums.length; j++) {
            for (int k=j+1; k<nums.length; k++) {

                int tempSum = nums[j] + nums[k];
                // diff는 j+k가 0과 얼마나 차이나는지에 대한 값
                int diff = 0 - tempSum;

                // diff로 key를 찾을 수 있다면, 그것을 더하는 순간 0이 되는 값이다.
                Integer i = map.get(diff);
                if (i != null) {
                    
                    // 이미 사용한 인덱스는 버려야 한다.
                    if (i == j || i == k) continue;
                    
                    List<Integer> sortedList = new ArrayList<>(Arrays.asList(nums[i], nums[j], nums[k]));
                    sortedList.sort(Comparator.naturalOrder());

                    answerSet.add(sortedList);
                }
            }
        }

        return new ArrayList<>(answerSet);
    }
}

돌기는 도는데 Runtime과 Memory 모두 참담하다.
어떻게 하면 줄일 수 있을까?

Solutions에 올라온 것들을 참고해 보니 놓치고 있던 핵심이 있다.
triplet의 순서가 상관이 없다는 점이다.

그래서 그런지 모두 일단 sort때리고 시작한다.
sort하게 되면 정렬된 값이기 때문에 중복을 건너뛰기가 매우 쉬워진다.

아래 내가 참고한 솔루션의 아이디어는 반복문에서 i를 고정해 두고 two pointer로 가능한 j, k를 모두 찾는것이다.

정렬되어있기 때문에 j++, k-- 통해서 알맞는 값을 찾을 수 있다.
i를 기준으로 j, k값만 변화시킨다는 점에서 O(n^2)인 점은 같다.

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        
        Arrays.sort(nums);

        List<List<Integer>> answer = new ArrayList<>();
        
        for (int i=0; i<nums.length; i++) {
            // 중복제거 - 중복 원소 중 제일 앞의 것만 쓴다. 어차피 i에 대한 값이 겹치는 경우가 없어야 하기 때문
            if (i > 0 && nums[i] == nums[i-1]) continue;

            int j = i + 1;
            int k = nums.length - 1;

            while (j < k) {
                int sum = nums[i] + nums[j] + nums[k];

                if (sum == 0) {
                    answer.add(Arrays.asList(nums[i], nums[j], nums[k]));
                    j++;

                    // 중복제거 - j또한 중복될 수 있기 때문에 k보다 작은 동안 가장 뒤의 것을 쓴다.
                    while (nums[j] == nums[j-1] && j < k) {
                        j++;
                    }

                    continue;
                }

                if (sum < 0) {
                    j++;
                } else {
                    k--;
                }
            }
        }

        return answer;
    }
}