package com.zmz.algorithm.hashtable;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author 张明泽
 * Create by 2022/5/31 14:46
 * 三数之和
 * LeetCode-15
 */
public class ThreeTogether {
    public static void main(String[] args) {
        int[] nums = { -1,0,1,2,-1,-4};
        List<List<Integer>> result = threeSum(nums);
        System.out.println(result);
    }

    /**
     * 双指针解法
     */
    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> lists = new ArrayList<>();
        // 排序
        Arrays.sort(nums);
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            // 排好序后第一个元素都大于0,一定就没有等于0的情况了
            if (nums[i] > 0) return lists;
            // 如果重复元素,跳过,避免出现重复解
            if (i > 0 && nums[i] == nums[i-1]) continue;
            // 当前指向的元素
            int curr = nums[i];
            // 左右指针
            int L = i + 1;
            int R = len - 1;
            while (L < R) {
                int tmp = curr + nums[L] + nums[R]; // 和
                if (tmp == 0) {
                    List<Integer> list = new ArrayList<>();
                    list.add(curr);
                    list.add(nums[L]);
                    list.add(nums[R]);
                    lists.add(list);
                    // 判断左边界是否和一下位置重复,去除重复解,往后移动
                    while(L < R && nums[L+1] == nums[L]) ++L;
                    // 判断右边界是否和一下位置重复,去除重复解,往后移动
                    while (L < R && nums[R-1] == nums[R]) --R;
                    // 分别移动
                    ++L;
                    --R;
                } else if (tmp < 0) { // 数太小了,左边界移动
                    ++L;
                } else { // 数太大了,有边界移动
                    --R;
                }
            }
        }
        return lists;
    }

    /**
     * 练习
     */
    public static List<List<Integer>> test(int[] nums) {
        List<List<Integer>> lists = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) return lists;
            if (i > 0 && nums[i] == nums[i-1]) continue;
            int left = i + 1;
            int right = nums.length - 1;
            while (left < right) {
                if (nums[i] + nums[left] + nums[right] == 0) {
                    ArrayList list = new ArrayList();
                    list.add(nums[i]);
                    list.add(nums[left]);
                    list.add(nums[right]);
                    lists.add(list);
                    while (left < right && nums[left] == nums[left + 1]) left++;
                    while (left < right && nums[right] == nums[right - 1]) right--;
                    left++;
                    right--;
                }
                else if (nums[i] + nums[left] + nums[right] < 0) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        return lists;
    }
}