package com.lsy.leetcodehot100;

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

public class _Hot6_三数之和 {
    public static List<List<Integer>> threeSum(int[] nums) {

        //先排序数组
        Arrays.sort(nums);
        //存放结果集
        List<List<Integer>> result = new ArrayList<>();

        //这里长度-2是为了保证可以组成三个数
        for(int oneNum=0;oneNum<nums.length-2;oneNum++){
            //数组排序后，如果当前元素大于0，说明剩下的元素也不可能为0
            if(nums[oneNum] > 0) break;

            //判断前一个元素是否和当前元素相等，若相等跳出循环，因为避免重复
            if(oneNum >0 && oneNum == nums[oneNum-1]) continue;

            //一个取oneNum后的数字
            int twoNum = oneNum +1;
            //一个从取最后一位
            int threeNum = nums.length-1;

            while(twoNum < threeNum){
                int sum = nums[oneNum]+ nums[twoNum]+nums[threeNum];
                if(sum <0){ //因为和小于0 说明twoNum需要向后移
                    while(twoNum < threeNum && nums[twoNum] == nums[++twoNum]);
                }else if(sum > 0){//因为和大于0 说明threeNum需要向前移
                    while(twoNum < threeNum && nums[threeNum] == nums[--threeNum]);
                }else{ //就存入list
                    List<Integer> resultList = Arrays.asList(nums[oneNum], nums[twoNum], nums[threeNum]);
                    result.add(resultList);

                    while(twoNum < threeNum && nums[twoNum] == nums[++twoNum]);
                    while(twoNum < threeNum && nums[threeNum] == nums[--threeNum]);

                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int []nums={-1,0,1,2,-1,-4};

        List<List<Integer>> lists = threeSum(nums);
        for (List<Integer> list : lists) {
            System.out.println(list);
        }
    }
}