题解 | #三数之和#

import java.util.*;


public class Solution {
   //三数之和：先找到一个数，然后在剩余数中利用双指针、
//    找到另外两个数值为相反数即可
    public ArrayList<ArrayList<Integer>> threeSum (int[] num) {
        ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
        int n = num.length;
        if(n<3){
            return ret;
        }
        // 有序
        Arrays.sort(num);
        //截至到n-2
        for(int i=0;i<n;i++){
            
            //去重跳过已经固定过的元素
            if(i>0&&num[i]==num[i-1]){
                continue; //跳出此次迭代。 //如果通过i++跳出迭代，直接到下一个会造成数组越界，因为如果是最后两个重复，
            }
            int l = i+1;
            int r = n-1;

            int a = num[i];
            // tmp.add(a); 在后面一起加入以免没有和为0，之和加入的tmp为a
            while(l<r){
               
                if(num[l]+num[r]==-a){
                    ArrayList<Integer> tmp = new ArrayList<>();
          
                    tmp.add(num[i]);
                    tmp.add(num[l]);
                    tmp.add(num[r]);
                    //有就加入，没有就不加入
                    ret.add(tmp);
                    //加入之后，判断如果遇到后面的重复元素跳过
 //跳过重复的元素去重
                    while(l+1<r&&num[l]==num[l+1]){
                    l++;
                     }
                     while(r-1>l&&num[r]==num[r-1]){
                    r--;
                     }
                     //双指针向中间移动
                     l++;
                     r--;
                }else if(num[l]+num[r]>-a){
                    //说明大了，右指针要--
                    r--;
                }else{
                    //小了。l++
                    l++;
                }
                
        
            }
        
        }

        return ret;
    }

}