Will the Guru

class Solution {
    /**
    Solution #1. a+b+c = 0  은, a+b = -c 와 같으므로, 그 숫자를 찾아보자.
    1. 배열을 우선 정렬한다.
    1-1. c를 0 ~ n-1 까지 순회
    2. start + end 와 c 를 비교
    2-1. start + end > c: end--;
    2-2. start + end == c: return;
    2-3. start + end < c: start++;
    */
    // public List<List<Integer>> threeSum(int[] nums) {
    //     Set<List<Integer>> resultSet = new HashSet<>();
    //     Arrays.sort(nums);
    //     int n = nums.length;
    //     for (int i=n-1;i>=0;i--) {
    //         int c = nums[i];
    //         int start = 0;
    //         int end = i - 1;
    //         while (start < end) {
    //             int a = nums[start];
    //             int b = nums[end];
    // 
    //             if (a + b > (c * -1)) {
    //                 end--;
    //             } else if (a + b == (c * -1)) {
    //                 resultSet.add(new ArrayList<>(Arrays.asList(a,b,c)));
    //                 start++;
    //             } else {
    //                 start++;
    //             }
    //         }
    //     }
    // 
    //     return new ArrayList<>(resultSet);  
    // }


    /**
    Solution #2. HashSet(visited) 이용하고 Solution #1 과 동일하게 a+b+c = 0 이라고 하면, a+b = -c 인 것을 찾아보자.
    1. 배열을 정렬한다
     1-1. c를 0 ~ n-1 까지 순회
    2. a 를 c의 index +1 부터 순회 => https://leetcode.com/problems/two-sum/editorial/#approach-3-one-pass-hash-table 참고
     2-1. HashSet(visited) 에 -(a+c) 인 것이 있는지 확인
      2-1-1. 있다면 result에 (a,b,c) 추가. a는 겹치지 않는 숫자까지 인덱스++;
     2-2. HashSet(visited)에 a 추가
     */
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        Set<Integer> visited;
        List<List<Integer>> result = new ArrayList<>();
        for (int i=0;i<nums.length;i++) {
            visited = new HashSet<>();
            int c = nums[i];

            if (i == 0 || nums[i-1] != nums[i]) {
                for (int j=i+1;j<nums.length;j++) {
                    int a = nums[j];

                    int b = (a + c) * (-1);
                    if (visited.contains(b)) {
                        result.add(Arrays.asList(a, b, c));
                        while (j + 1 < nums.length && nums[j] == nums[j+1]) {
                            j++;
                        }
                    }
                    visited.add(a);
                }
            }
        }

        return result;
    }


    private void print(int[] nums) {
        for (int num: nums) {
            System.out.print(num + " ");
        }
        System.out.println("");
    }
}