15. 3Sum

    public List<List<Integer>> threeSum(int[] nums) {
        // result
        HashSet<List<Integer>> result = new HashSet<>();
        // bound
        if (nums.length < 3) {
            return new ArrayList<>();
        }
        // sort
        Arrays.sort(nums);
        // out loop
        for (int i = 0; i < nums.length - 2; i++) {
            // tow pointer close
            int j = i + 1;
            int k = nums.length - 1;
            while (j < k) {
                int sum = nums[i] + nums[j] + nums[k];
                if (sum == 0) {
                    result.add(Arrays.asList(nums[i], nums[j++], nums[k--]));
                }else if (sum < 0) {
                    j++;
                }else if (sum > 0) {
                    k--;
                }
            }
        }
        return new ArrayList<>(result);
    }

    public List<List<Integer>> threeSum(int[] nums) {
        if (nums.length < 3) {
            return new ArrayList<>();
        }
        HashSet<List<Integer>> result = new HashSet<>();
        HashMap<Integer ,Integer> map = new HashMap();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i],i);
        }
        for (int i = 0; i < nums.length - 2; i++) {
            if (i >=1 && nums[i] == nums[i - 1]) {
                continue;
            }
            for (int j = i + 1; j < nums.length - 1; j++) {
                int target = -nums[i] - nums[j];
                // map.get(target) > j 防止重复包含自己
                if (map.containsKey(target) && map.get(target) > j) {
                    result.add(Arrays.asList(nums[i], target, nums[j]));
                }
            }
        }
        return new ArrayList<>(result);
    }