题解 | #三数之和#

import java.util.*;
public class Solution {
    
    public class CompareInteger implements Comparator<Integer> {
        @Override
        public int compare(Integer num1, Integer num2) {
            return num1 - num2;
        }
    }
    
    public class CompareArrayList implements Comparator<ArrayList<Integer>> {
        @Override
        public int compare(ArrayList<Integer> num1, ArrayList<Integer> num2) {
            for (int i = 0; i < num1.size(); i++) {
                if (num1.get(i) < num2.get(i)) {
                    return -1;
                }
                else if (num1.get(i) > num2.get(i)){
                    return 1;
                }
            }
            return 0;
        }
    }
    
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        ArrayList<ArrayList<Integer>> threeTuples = new ArrayList<>();
        if (3 > num.length) {
            return threeTuples;
        }
        
        ArrayList<Integer> positiveList = new ArrayList<>(); // 存放正数
        ArrayList<Integer> zeroList = new ArrayList<>(); // 存放 0
        ArrayList<Integer> negativeList = new ArrayList<>(); // 存放负数
        
        HashMap<Integer, Integer> hashMap = new HashMap<>(); // 每个数有多少个
        
        int sum = 0;
        
        // 构造数据
        for (int tmpValue : num) {
            if (tmpValue < 0) {
                negativeList.add(tmpValue);
            }
            else if (tmpValue == 0) {
                zeroList.add(tmpValue);
            }
            else {
                positiveList.add(tmpValue);
            }
            sum = hashMap.getOrDefault(tmpValue, 0);
            sum++;
            hashMap.put(tmpValue, sum);
        }
        
        // 一些特殊情况的处理
        if (0 == negativeList.size() || 0 == positiveList.size()) {
            if (hashMap.getOrDefault(0, 0) >= 3) {
                ArrayList<Integer> threeTuple = new ArrayList<>(3);
                for (int i = 0; i < 3; i++) {
                    threeTuple.add(0);
                }
                threeTuples.add(threeTuple);
                return threeTuples;
            }
            else {
                return threeTuples;
            }
        }
        
        // 具体代码实现
        int tmpValue = 0;
        for (int i : negativeList) {
            for (int j : positiveList) {
                tmpValue = 0 - (i + j);
                if (tmpValue == i || tmpValue == j) {
                    if (hashMap.get(tmpValue) > 1) {
                        ArrayList<Integer> threeTuple = new ArrayList<>(3);
                        threeTuple.add(i);
                        threeTuple.add(j);
                        threeTuple.add(tmpValue);
                        threeTuple.sort(new CompareInteger());
                        if (!threeTuples.contains(threeTuple)) {
                        // if (isValid(threeTuples, threeTuple)) {
                            threeTuples.add(threeTuple);
                        }
                    }
                }
                else {
                    if (hashMap.getOrDefault(tmpValue, 0) != 0) {
                        ArrayList<Integer> threeTuple = new ArrayList<>(3);
                        threeTuple.add(i);
                        threeTuple.add(j);
                        threeTuple.add(tmpValue);
                        threeTuple.sort(new CompareInteger());
                        if (!threeTuples.contains(threeTuple)) {
                        // if (isValid(threeTuples, threeTuple)) {
                            threeTuples.add(threeTuple);
                        }
                    }
                }
            }
        }
        if (hashMap.getOrDefault(0, 0) >= 3) {
            ArrayList<Integer> threeTuple = new ArrayList<>(3);
            for (int i = 0; i < 3; i++) {
                threeTuple.add(0);
            }
            threeTuples.add(threeTuple);
        }
        threeTuples.sort(new CompareArrayList());
        return threeTuples;
    }
    
//     public boolean isValid(ArrayList<ArrayList<Integer>> threeTuples, ArrayList<Integer> threeTuple) {
//         boolean rs = true;
//         for (ArrayList<Integer> tmp : threeTuples) {
//             if (isEqual(tmp, threeTuple)) {
//                 rs = false;
//                 break;
//             }
//         }
//         return rs;
//     }
    
//     public boolean isEqual(ArrayList<Integer> nums1, ArrayList<Integer> nums2) {
//         boolean rs = true;
//         for (int i = 0; i < nums1.size(); i++) {
//             if (nums1.get(i) != nums2.get(i)) {
//                 rs = false;
//                 break;
//             }
//         }
//         return rs;
//     }
}