[force deduction] sum of three numbers

Give you one containing n Array of integers  nums, Judge  nums  Are there three elements in a,b,c , bring  a + b + c = 0 ？ Please find out all and for 0 And No repetition Triple of .

Be careful ： Answer cannot contain duplicate triples .

Example 1：

Input ：nums = [-1,0,1,2,-1,-4]
Output ：[[-1,-1,2],[-1,0,1]]

Example 2：

Input ：nums = []
Output ：[]

Example 3：

Input ：nums = [0]
Output ：[]

Tips ：

0 <= nums.length <= 3000
-105 <= nums[i] <= 105

Mode one ： adopt Set Gather to judge

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> list=new ArrayList<>();
        if(nums.length<3) return list;
        Arrays.sort(nums);
        for(int i=0;i<nums.length;i++){
            // If the first element after sorting is greater than 0, Then the following elements are greater than 0, non-existent 3 The sum of the numbers is 0
            if(nums[i]>0) break;
            // First number 
            int first=nums[i];
            // Exclude duplicates 
            if(i>0&&nums[i]==nums[i-1]) continue;

            Set<Integer> set=new HashSet<>();// Put it in the outer circulation , Each cycle is recreated set aggregate 
            for(int j=i+1;j<nums.length;j++){
                // The third number 
                int third=nums[j];
                int second=-(first+third);// The first number and the second number add and negate to form the third number 
                if(set.contains(second)){
                    //Arrays.asList() Convert array to List aggregate 
                    list.add(new ArrayList<>(Arrays.asList(first,third,-(first+third))));
                    while(j < nums.length - 1 && nums[j] == nums[j + 1]) j++;// duplicate removal 
                }
                set.add(third);// Store the third number in the set , Because the third number is the original number in the array , Use it with second Compare , Instead of putting second Deposit in set in 
            }
        }
        return list;
    }
}

Mode two ： Double pointer

ublic class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> list=new ArrayList<>();
        // Sentenced to empty , And judge whether the array length is less than 3
        if(nums==null || nums.length<3) return list;
        Arrays.sort(nums); // Sort 
        for(int i=0;i<nums.length-1;i++){
            if(nums[i]>0) break;// If the first element after sorting is greater than 0, Then the following elements are greater than 0, non-existent 3 The sum of the numbers is 0
            if(i>0 && nums[i]==nums[i-1]) continue; // Filter duplicates 
            int middle=-nums[i];
            // Define double pointer 
            int left=i+1,right=nums.length-1;
            while(left<right){
                if(nums[left]+nums[right]>middle){// It indicates that the positive number selected is too large , The right pointer should move to the left 
                    right--;
                }else if(nums[left]+nums[right]<middle){// It means that the negative number is too small ,left Should move to the right 
                    left++;
                }else{ //ums[left]+nums[right]==middle
                    list.add(new ArrayList<>(Arrays.asList(nums[left],nums[i],nums[right])));//Arrays.asList() Convert array to List aggregate 
                    // The pointer continues to move 
                    left++;
                    right--;
                    while(left<right && nums[left]==nums[left-1]) left++;// duplicate removal 
                    while(left<right && nums[right]==nums[right+1]) right--;
                }
            }
        }
        return list;
    }
    public static void main(String[] args) {
        Solution s=new Solution();
        System.out.println(s.threeSum(new int[]{-1,0,1,2,-1,-4}));
    }
}