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

首先，我们先对数组进行排序处理。
然后，确定固定指针i，与双指针j，k。其中固定位从0开始，j从i起始的下一位向左移动，k从数组末端向右移动。
①提前结束的条件 num[i]>0
因为i < j < k，所以num[i]>=num[j]>=num[k]。因此如果num[i]>0，不可能使三个大于0的数之和等于0
②重复数字跳过
在有序数组中，如果遍历当相邻位的值相同，直接跳过。
③循环流程
如果三数之和sum>0，k向左移动
如果sum<0，j向右移动
如果sum == 0，记录i、j、k
i、j继续移动寻找当前固定指针下的其他解，直到左右指针碰撞结束循环。
固定指针向前移动，并开始新循环。
固定指针时间复杂度O(N)，移动指针ij时间复杂度O(N)，嵌套之后时间复杂度O(N)

import java.util.ArrayList;
import java.util.Arrays;

public class Solution {
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {'
        //先对数组进行排序
        Arrays.sort(num);
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        for(int i=0; i<num.length-2; i++){
            int j = i + 1, k = num.length - 1;
            //如果固定位大于0，已经不可能找到三数和为0的数，提前退出
            if(num[i] > 0)break;
            //如果相邻数重复，直接跳过
            if(i > 0 && num[i] == num[i-1])continue;
            while(j < k){
                int sum = num[i] + num[j] + num[k];
                if(sum > 0){
                    while(j < k && num[k] == num[--k]);
                }
                else if(sum < 0){
                    while(j < k && num[j] == num[++j]);
                }
                else{
                    res.add(new ArrayList<Integer>(Arrays.asList(num[i], num[j], num[k])));
                    while(j < k && num[k] == num[--k]);
                    while(j < k && num[j] == num[++j]);
                }
            }
        }
        return res;
    }
}