15. 3sum

배열 내의 3가지 요소의 합이 0이 되는 경우를 찾는 문제.

투포인터의 변형문제로, 값 1개를 정해두고, 나머지 두개의 합이 해당 값과 같은지 비교하면 된다.

여기까지는 무난하게 풀 수 있으나,

 

Notice that the solution set must not contain duplicate triplets.
중복되는 세 쌍이 있으면 안 된다는 추가 조건때문에 시간이 조금 더 걸렸다.

 

처음에는 Set<List>을 사용해서 중복을 확인하려 했으나, List의 경우 참조값을 저장하기 때문에 값이 전부 동일해도 다른 객체로 인식해서 실패하였다.

그다음에는 Map을 사용해보려 했으나 (Map<target, 나머지 두개중 첫번째 수>) 동일한 target에 대해 다른 합이 존재할 수 있으므로 이것도 실패하였다.

while문을 사용해서, 동일한 target, start, end가 나오면 skip하게끔 수정해서 성공!

 

Q.

target의 경우 skip할 필요가 없지 않나? 라고 생각할 수 있지만

A.

-4,-4,-2,-2,-2 의 경우 target이 0번째 index의 -4일때는 (2번째 Index) + (3번째 index)로 하나의 답이 나올 수 있고

-4,-4,-2,-2,-2 의 경우 target이 1번째 index의 -4일때는 (2번째 Index) + (3번째 index)로 또다시 동일한 답이 나올 수 있다.

따라서 target도 동일한 target이 나오면 넘어가야 한다!

public static List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();

        for (int t = 0; t <= nums.length - 3; t++) {
            if (t > 0 && nums[t] == nums[t - 1]) continue;
            int target = nums[t], start = t + 1, end = nums.length - 1;
            while (start < end) {
                int sum = nums[start] + nums[end];
                if (sum + target == 0) {
                    ans.add(new ArrayList<>(Arrays.asList(target, nums[start], nums[end])));
                    while (start < end && nums[start] == nums[start + 1]) start++;
                    while (start < end && nums[end] == nums[end - 1]) end--;
                    start++;
                    end--;
                } else if (sum + target > 0) {
                    end--;
                } else if (sum + target < 0) {
                    start++;
                }
            }
        }
        return ans;
    }