题解 | #三数之和#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param num int整型一维数组
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> threeSum (int[] num) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        if (num.length < 3) {
            return res;
        }
        margeSrt(num, new int[num.length], 0, num.length - 1);

        for (int a = 0; a < num.length; a++) {
            if (a > 0 && num[a] == num[a - 1]) {
                continue;
            }
            if (num[a] > 0) {
                break;
            }
            for (int b = a + 1; b < num.length; b++) {
                if (b > a + 1 && num[b] == num[b - 1]) {
                    continue;
                }
                if (num[a] + num[b] > 0) {
                    break;
                }
                for (int c = b + 1; c < num.length; c++) {
                    if (c > b + 1 && num[c] == num[c - 1]) {
                        continue;
                    }

                    int sum = num[a] + num[b] + num[c];

                    if (sum > 0) {
                        break;
                    }
                    if (sum == 0) {
                        ArrayList<Integer> vs = new ArrayList<>();
                        vs.add(num[a]);
                        vs.add(num[b]);
                        vs.add(num[c]);
                        res.add(vs);
                    }
                }
            }
        }


        return res;
    }

    public void margeSrt(int [] num, int [] tmp, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = left + (right - left) / 2;
        margeSrt(num, tmp, left, mid);
        margeSrt(num, tmp,  mid + 1, right);

        int k = 0, i = left, j = mid + 1;
        while (i <= mid && j <= right) {
            if (num[i] > num[j]) {
                tmp[k++] = num[j++];
            } else {
                tmp[k++] = num[i++];
            }
        }
        while (i <= mid) {
            tmp[k++] = num[i++];
        }
        while (j <= right) {
            tmp[k++] = num[j++];
        }
        for (int ni = left, ti = 0; ni <= right; ni++, ti++) {
            num[ni] = tmp[ti];
        }
    }
}