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

import java.util.*;
public class Solution {
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
        if(num.length<3) return list;
        int[] A = new int[201]; //创建201个桶
        for(int i : num) A[i+100]++; //使所有元素为非负，且统计个数
        
        for(int i = 0;i<201;i++){
            if(A[i]==0) continue;
            A[i]--;
            for(int j = 0;j<201&&(i+j)<301;j++){
                if(A[j]==0) continue;
                A[j]--;
                if(A[300-i-j]>0){ // 由于前面每个元素+100，因此需寻找和为300的
                    int tmp1[] = new int[]{i-100,j-100,200-i-j};//恢复为原始元素
                    Arrays.sort(tmp1);
                    ArrayList<Integer> tmp = new ArrayList<Integer>();
                    tmp.add(tmp1[0]);
                    tmp.add(tmp1[1]);
                    tmp.add(tmp1[2]);
                    if(list.contains(tmp)){}//若已包含，则不再add
                    else
                        list.add(tmp);
                    
                }
                A[j]++;
            }
            A[i]++;
        }
        
        return list;
    }
}