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

/**
 * @author wuze
 * @desc ...
 * @date 2021-03-16 11:51:28
 */
public class 三数之和_字节高频2_15 {
    public List<List<Integer>> threeSum(int[] nums) {

        //思路：
        //有三个数，去重时要两两比较 （x）
        //技巧：先排序！！！定住其中一个数i（nums[i]==nums[i-1]时也去重），然后剩下两个数直接 比较，相等就去重 ！（Y）
        //      双指针，一个从头（i）开始，一个从尾（len-1）开始
        //技巧：对于字符数组（字符串数组），没思路时，就对其排序！
        List<List<Integer>> list = new ArrayList<List<Integer>>();


        //必须要先排序，因为待会用左右指针遍历时，只要左右指针都不等于它的相邻元素，就可以达到去重效果
        Arrays.sort(nums);

        int len=nums.length;
        //遍历指示指针
        int left=0;
        int right=0;
        int sum=0;

        //对每一个数都进行 左右指针 遍历 判断
        for(int i=0;i<len;i++){

            //左指针
            left=i+1;
            //右指针
            right=len-1;

            //去重 定点 重复值
            if(i>0 && nums[i]==nums[i-1]){
                continue;
            }

            //对每一个i，都进行 left和right的移动遍历
            while(left<right){
                sum=nums[i]+nums[left]+nums[right];
                if(sum==0){
                    List<Integer> level = new ArrayList<>();
                    //添加
                    level.add(nums[i]);
                    level.add(nums[left]);
                    level.add(nums[right]);
                    list.add(level);

                    //去重(前提：数组是排序的)
                    while(left<right && nums[left]==nums[left+1]){
                        left++;
                    }
                    while(left<right && nums[right]==nums[right-1]){
                        right--;
                    }
                    //去重完毕再次移动指针到下一个点位
                    left++;
                    right--;
                }else if(sum<0){
                    left++;
                }else{
                    right--;
                }
            }

        }

        return list;
    }
}