题解 | #数组中相加和为0的三元组#

import java.util.*;
//采用2层循环和左右双指针，时间复杂度：O(n^2),空间复杂度：O(n^2)
public class Solution {
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        ArrayList<ArrayList<Integer>> array = new ArrayList<ArrayList<Integer>>();//创建一个对象ArrayList<ArrayList<Integer>>
        int length = num.length;
        //特殊值处理
        if(length<3){
            return array;
        }
        Arrays.sort(num);//排序，根据结果要求
        //采用2层循环，和左右指针，左右指针可以代替第三层循环
        int left=0;//左指针
        int right=0;//右指针
        for(int i=0;i<length-2;i++){//第一层循环，从0-length-2遍历，该数是三个数中最小的
            left = i+1;//初始化左指针
            right = length-1;//初始化右指针
            while(left<right){//第二层循环遍历，左右指针左右来回移动，可以起到两层循环作用
                if(num[i]>0){//如果最小的数都大于0，则往后也不会存在三个数相加等于0，结束循环
                    break;
                }
                if(num[i] + num[left] + num[right] == 0){//三个数相加等于0
                    ArrayList<Integer> arr = new ArrayList<>();//创建一个临时对象ArrayList<Integer>，保存三元组，每次进入都需要创建，并且保证该对象不会被修改，否则会影响对象array。
                    arr.add(num[i]);
                    arr.add(num[left]);
                    arr.add(num[right]);
                    array.add(arr);//保存三元组
                    left++;//左指针向右移动
                    right--;//右指针向左移动
                }else if(num[i] + num[left] + num[right] < 0){//三个数相加小于0
                    left++;//左指针向右移动
                }else{//三个数相加大于0
                    right--;//右指针向左移动
                }
            }
        }
        
        //循环遍历去重复元素
        for(int i=0;i<array.size()-1;i++){
            for(int j=i+1;j<array.size();j++){
                if(array.get(i).get(0)==array.get(j).get(0) && array.get(i).get(1)==array.get(j).get(1) && array.get(i).get(2)==array.get(j).get(2)){
                    array.remove(j);
                    j--;
                }
            }
        }
        
        return array;
    }
}