给出一个有n个元素的数组S，S中是否有元素a,b,c满足a+b+c=0？

╰半橙微兮° 2023-01-07 07:08 133阅读 0赞

# 题目描述 #

给出一个有n个元素的数组S，S中是否有元素a,b,c满足a+b+c=0？找出数组S中所有满足条件的三元组。

*  注意：  
    三元组（a、b、c）中的元素必须按非降序排列。（即a≤b≤c）  
    解集中不能包含重复的三元组。  
    例如，给定的数组 S = \{-10 0 10 20 -10 -40\},解集为(-10, 0, 10) (-10, -10, 20)

# 示例1 #

输入

[-2,0,1,1,2]

返回值

[[-2,0,2],[-2,1,1]]

# Java实现 #

import java.util.*;
    /**
     * （1）首先对数组进行排序（从小到大）
     * （2）依次取出第 i 个数（i从0开始），并且不重复的选取（跳过重复的数）
     * （3）这样问题就转换为 2 个数求和的问题（可以用双指针解决方法）
     *  2 数求和问题
     *     （4）定义两个指针：左指针（left） 和 右指针（right）
     *     （5）找出固定 left， 此时left所指的位置为数组中最小数，再找到两个数和 不大于 target 的最大 right 的位置
     *     （6）调整 left 的位置（后移），求解和是否为 target O(n)
     *     （7）时间复杂度：O(nlogn) + O(n*n)
    */
    public class Solution {
        
        public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        
           ArrayList<ArrayList<Integer>> result = new ArrayList<>();
            
            ArrayList<Integer> list;
            //quickSort(num,0,num.length-1);
           Arrays.sort(num);
            for(int i = 0;i < num.length - 2; i ++){
        
                if(i == 0 || num[i] != num[i-1]){
        
                    int left = i + 1;
                    int right = num.length - 1;
                    while(left < right){
        
                        while(left < right && (num[i] + num[left] + num[right]) > 0){
        
                            right --;
                        }
                        if(left < right && (num[i] + num[left] + num[right]) == 0){
        
                            list = new ArrayList<>();
                            list.add(num[i]);
                            list.add(num[left]);
                            list.add(num[right]);
                            result.add(list);
                            while(left < right && num[left] == list.get(1)){
        
                                left ++;
                            } 
                        }else{
        
                                left ++;
                        }
                    }
                }
                
            }
            return result;
        }
    }