题解 | #三数之和#

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

public class Solution {
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        if (num == null || num.length < 3) return new ArrayList<>(0);
        
        Arrays.sort(num);//排序处理，方便后面去重

        //存放原数组的相反数，key为原数组值，value为原数组下标。之所以用Map，是因为需要去重，保留最后一个下标的数即可。
        HashMap<Integer, Integer> map = new HashMap<>((int) (num.length / 0.75f + 0.5));
        
        for (int i = 0; i < num.length; i++) {//初始化相反数map集合
            map.put(Math.negateExact(num[i]), i);
        }

        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        for (int i = 0; i < num.length - 2; i++) {
            if (i != 0 && num[i] == num[i - 1]) continue;//同样的值，前面已经计算过了，跳过

            for (int j = i + 1; j < num.length - 1; j++) {
                if (j != i + 1 && num[j] == num[j - 1]) continue;//同样的值，前面已经计算过了，跳过

                int temp = num[i] + num[j];
                if (!map.containsKey(temp)) {
                    continue;
                }

                int k = map.get(temp);

                if (k > j) {
                    result.add(new ArrayList<>(Arrays.asList(num[i], num[j], num[k])));
                }
            }
        }

        return result;
    }
}

空间复杂度：O(n)；时间复杂度：O(n^2)