/**
1.  a + b + c = 0 确定一个值a后, 因为和不变, 如果b增大. c 必然减少, 符合单调性, 所以可以排序后用双指针处理
2. 在确定a, 并且遍历完a相关的所有组合后a必定不会再次出现, 可以直接跳过
*/

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Map<Integer, Integer> locate = new HashMap<>();
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        int n = nums.length;
        for (int i = 0 ; i < n ; i ++){
            int a = nums[i];
            if (i > 0 && nums[i-1] == a) continue;

            for (int l = i + 1, r = n - 1 ; l < r ; l++ , r--){
                int sum = a + nums[l] + nums[r];
                if (sum > 0)        l--;
                else if (sum < 0)   r++;
                else {
                    int[] answer = {a, nums[l], nums[r]};
                    result.add(Arrays.stream(answer).boxed().collect(Collectors.toList()));
                    while (l < r && nums[l] == nums[l+1]) l++;
                    while (l < r && nums[r] == nums[r-1]) r--;
                }
            }
        }
        return result;
    }
}