题解 | #三数之和#

import java.util.*;
public class Solution {
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        //把输出的内容弄好
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        //当输入数据不够三元组时候，输出空
        if(num.length <= 2){
            return res;
        }
        //将数组排序
        Arrays.sort(num);
        int n = num.length;
        //对于排序好的数组，利用二分法，找到两个数字的和符合要求
        //这里限定范围，留了两个，是因为三元组，后面还有两个数字
        for(int i = 0; i<n-2;i++){
            //当前一个与前一个数字相等，则跳过,>0 是防止越界
            if(i>0 && num[i] == num[i-1]){
                continue;
            }
            //对于每一个数字，找另外两个数求和，是它的相反数，那么三个数相加，结果就是0
            int target = -num[i];
            //对于每一个数字，就是一个单独的二分法，定义左指针和右指针
            int left = i+1;
            int right = n - 1;
            while(left < right){
                if(num[left] + num[right] == target){
                    //这里面能保证顺序，因为排序之后，i是最前面的
                    ArrayList<Integer> temp = new ArrayList<>();
                    temp.add(num[i]);
                    temp.add(num[left]);
                    temp.add(num[right]);
                    res.add(temp);
                    left++;
                    right--;
                    //可能存在数字重复情况
                    while(left < right && num[left] == num[left - 1]){
                        left++;
                    }
                    while(left < right && num[right] == num[right + 1]){
                        right--;
                    }
                }
                else if(num[left] + num[right] > target){
                    right--;
                }
                else{
                    left++;
                }
            }
        }
        return res;


    }
}

这里面包含两次遍历，第一次是遍历数组拿到target，这里面不能有重复的，重复continue来解决，这里要注意越界问题，要保证i>0才可以实现。然后再遍历找left和right，不能有重复元素，所以当left与-1相等，应该跳过，同理，right也是，与+1相等也要跳过。