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));
    }
}