package arrays;

import java.util.*;

/**
 * 题目:给定一个数组,求相加等于0的三个数,不能重复
 *
 * @Author Gavin
 * @date 2022年01月03日 10:06
 */
public class array_10 {
 /**
 * 第一种方法:暴力破解法,使用三层for循环
 */
 //Time:O(n^3) Space:O(n)
 public List<List<Integer>> solution_1(int[] nums) {
 List<List<Integer>> result = new ArrayList<>();
 Set<List<Integer>> set = new HashSet<>();
 Arrays.sort(nums);
 for (int i = 0; i < nums.length; i++) {
 for (int j = i + 1; j < nums.length; j++) {
 for (int k = j + 1; k < nums.length; k++) {
 if (nums[i] + nums[j] + nums[k] == 0) {
 List<Integer> elem = Arrays.asList(nums[i], nums[j], nums[k]);
 if (set.contains(elem)) continue;//注意,set判断集合是否相等需要集合里面的元素完全相同,顺序也要一样
 set.add(elem);
 result.add(elem);
 }
 }
 }
 }
 return result;
 }

 /**
 * 第二种方法:使用两个游标来处理
 * 思路:首先对数组进行排序,然后指定变量k指向数组末尾,然后另外两个变量i,j就从数组的0和k-1的位置开始循环,
 * 主要判断i+j的大小和k指向的大小和是否为0,然后i,j分别向中间移动,移动完之后第一轮查找就完了,然后k指向k-1的位置再进行第二轮
 * 的查找
 */
 //Time:O(n^2) Space:O(1)
 public List<List<Integer>> solution_2(int[] nums) {
 List<List<Integer>> result = new ArrayList<>();
 Arrays.sort(nums);
 for (int k = nums.length - 1; k >= 2; --k) {
 if (nums[k] < 0) break;//由于数组是排序了的,k是指向最大值,如果最大值都小于0,那么整个数组都小于0了
 int target = -nums[k], i = 0, j = k - 1;
 while (i < j) {
 if (nums[i] + nums[j] == target) {
 result.add(Arrays.asList(nums[i], nums[j], nums[k]));
 //跳过相同的元素
 while (i < j && nums[i + 1] == nums[i]) ++i;
 while (i < j && nums[j - 1] == nums[j]) --j;
 ++i;
 --j;
 } else if (nums[i] + nums[j] < target) {
 ++i;
 } else {
 --j;
 }
 }
 //跳过相同的k值
 while (k >= 2 && nums[k - 1] == nums[k]) --k;
 }
 return result;
 }

 public static void main(String[] args) {
 List<Integer> pre = new ArrayList<>();
 pre.add(1);
 pre.add(2);
 pre.add(3);
 Set<List<Integer>> set = new HashSet<>();
 set.add(pre);

 List<Integer> pre2 = new ArrayList<>();
 pre2.add(1);
 pre2.add(3);
 pre2.add(2);

 System.out.println(set.contains(pre2));
 }
}