// @Title: 三数之和 (3Sum)
// @Author: qisiii
// @Date: 2022-03-04 09:46:33
// @Runtime: 25 ms
// @Memory: 45.2 MB
// @comment: 解析为两数之和，且通过双指针降低时间复杂度
// @flag: BLUE
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        if(nums.length<3){
            return new ArrayList();
        }
        Arrays.sort(nums);
        List<List<Integer>> result=new ArrayList();
        for(int i=0;i<nums.length;i++){
            if(i>0&&nums[i-1]==nums[i]){
                continue;
            }
         List<List<Integer>> temp= doThree(Arrays.copyOfRange(nums,i+1,nums.length),-nums[i]);
         if(temp!=null&&!temp.isEmpty()){
             result.addAll(temp);
         }
        }
        return result;
    }
    public List<List<Integer>> doThree(int[] nums,int target){
        List<List<Integer>> result=new ArrayList();
        int left=0;
        int right=nums.length-1;
        while (left<right){
            if(nums[left]+nums[right]==target){
                    List<Integer> temp=new ArrayList();
                temp.add(-target);
                temp.add(nums[left]);
                temp.add(nums[right]);
                result.add(temp);
                left++;
                right--;
                while (left < right && nums[left] == nums[left - 1]) left++;
                    while (left < right && nums[right] == nums[right + 1]) right--;
                continue;
            }else if (nums[left]+nums[right]<target){
                left++;
            }else{
                right--;
            }
        }
        return result;
    }
}

// @Title: 三数之和 (3Sum)
// @Author: qisiii
// @Date: 2024-04-12 17:27:31
// @Runtime: 34 ms
// @Memory: 50.3 MB
// @comment: 英雄哪里出来的思路，排序+双指针
// @flag: WHITE
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int left=i+1;
            int right=nums.length-1;
            int target=-nums[i];
            while(left<right){
                if(nums[left]+nums[right]>target){
                    right--;
                }else if(nums[left]+nums[right]<target){
                    left++;
                }else{
                    ans.add(Arrays.asList(nums[i],nums[left],nums[right]));
                    left++;
                    right--;
                    while(left<nums.length&&nums[left]==nums[left-1]){
                        left++;
                    }
                    while(right>=0&&nums[right]==nums[right+1]){
                        right--;
                    }
                }
            }
        }
        return ans;
    }

    
}