package question;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @author Roderland
 * @since 1.0
 */
public class Question15 {
 public static void main(String[] args) {
 int[] ints = {
 -1, 0, 1, 2, -1, -4
 };
 new Question15().threeSum2(ints).forEach(System.out::println);
 }
 public List<List<Integer>> threeSum2(int[] nums) {
 List<List<Integer>> res = new LinkedList<>();
 Arrays.sort(nums);
 int n = nums.length;
 for (int i=0; i<n; i++) {
 if (i>0 && nums[i]==nums[i-1]) continue;
 int target = -nums[i];
 int j = i+1;
 int k = n-1;
 while (j<k) {
 int twoSum = nums[j]+nums[k];
 if (twoSum==target) {
 res.add(Arrays.asList(nums[i], nums[j], nums[k]));
 do j++;
 while (j < k && nums[j] == nums[j - 1]);
 } else if (twoSum<target) {
 j++;
 } else {
 k--;
 }
 }
 }
 return res;
 }


 public List<List<Integer>> threeSum(int[] nums) {
 List<List<Integer>> res = new LinkedList<>();
 Set<Flag> set = new HashSet<>();
 for (int i = 0; i < nums.length; i++) {
 int target = -nums[i];
 Map<Integer, Integer> map = new HashMap<>();
 for (int j = i+1; j < nums.length; j++) {
 map.put(target-nums[j], j);
 }
 for (int j = i+1; j < nums.length; j++) {
 if (map.containsKey(nums[j])) {
 if (map.get(nums[j])!=j) {
 int[] ints = {nums[i], nums[j], target - nums[j]};
 Arrays.sort(ints);
 Flag flag = new Flag(ints[0], ints[1], ints[2]);
 if (!set.contains(flag)) {
 set.add(flag);
 res.add(Arrays.stream(ints).boxed().collect(Collectors.toList()));
 }
 }
 }
 }
 }
 return res;
 }

 static class Flag {
 int x,y,z;

 public Flag(int x, int y, int z) {
 this.x = x;
 this.y = y;
 this.z = z;
 }

 @Override
 public boolean equals(Object o) {
 if (o==this) return true;
 if (!(o instanceof Flag)) return false;
 Flag flag = (Flag) o;
 return x== flag.x && y== flag.y && z== flag.z;
 }

 @Override
 public int hashCode() {
 int r = 17;
 r=31*r+x;
 r=31*r+y;
 r=31*r+z;
 return r;
 }
 }
}