3 Sum: Three Tracker in One Array

First Thoughts

하나를 기준으로 잡고 그럼 전형적인 투썸 문제와 똑같이 된다. 그럼 helper method를 사용해서 똑같이 하면 되지 않을까..하다가 너무 복잡해졌다..

Solution

주의: 시간 효율성이 매우 좋지 않다..아마 O(N^2) 5% 떴다

public List<List<Integer>> threeSum(int[] nums) {
	Set<List<Integer>> triples = new HashSet<>();
    if (nums.length < 3) return new ArrayList<>();
    Arrays.sort(nums);
    for (int i=0; i<nums.length; i++) {
    	int j = i+1;
        int k = nums.length-1;
        while (j < k) {
        	int sum = nums[i] + nums[j] + nums[k];
            if (sum==0) triples.add(Arrays.asList(nums[i], nums[j++], nums[k--]));
            else if (sum > 0) k--;
            else if (sum < 0) j++;
        }
    }
    return new ArrayList<>(triples);
}

Catch Point

1. 배열을 정렬함으로써 조금씩 값을 조정할 수 있게 되었다. 끝까지 0이 되지 않을때는 j가 k를 앞지르게 되어 끝나게 될 것이다.

2. 처음에 생각했던 것처럼 기준은 하나로 정해놓고 그에 따라 relative index를 두는게 로직상 이해하기 쉬운 것 같다.

3. 조정하는 과정이란 합이 너무 크면 조금 더 작은 값을 시도해보고, 반대로 합이 너무 작게 나오면 더 큰 값을 시도하는 것이다.