import java.util.*;

/**
 * @author mac
 * @date 2020/11/5-22:57
 */
public class t15_三数之和 {
    /**
     * 遍历+双指针法
     * 时间复杂度：O(n^2)，数组排序 O(NlogN)，遍历数组 O(n)， 双指针遍历 O(n)
     * 总体 O(NlogN)+O(n)?O(n)=O(n2)
     *
     * @param nums
     * @return
     */
    public List<List<Integer>> threeSum(int[] nums) {
        // 对数组进行排序
        Arrays.sort(nums);
        // 创建返回对象
        List<List<Integer>> res = new ArrayList<>();
        // 循环遍历数组，因为是三数和，所以做后一个判断数组nums倒数第三个就可以了，故k < nums.length - 2
        for (int k = 0; k < nums.length - 2; k++) {
            // 如果数组大于0了，就证明后面没有负数（提前排序过），那就不可能相加为0，故直接返回
            if (nums[k] > 0) {
                break;
            }
            // 遍历第一个数时0<1，k-1就小于0，故有k > 0 ，前一个和后一个想等的话，那么只判断后面的就可以了，两个都判断如果有三数和为0，接过重复
            if (k > 0 && nums[k] == nums[k - 1]) {
                continue;
            }
            // i指针1在k前一位，j指针有最后一位
            int i = k + 1, j = nums.length - 1;
            // 如果大于等于j，那么证明两个指针碰撞了，就不需要继续判断三数之和了
            while (i < j) {
                // 三数相加
                int sum = nums[k] + nums[i] + nums[j];
                // 因为最开始是排序过的，如果三数和小于0，那么i需要右→移去更大的数
                if (sum < 0) {
                    // 如i和i右面的数相同，就没有再去判断的必要了
                    while (i < j && nums[i] == nums[++i]) ;
                }
                // // 因为最开始是排序过的，如果三数和大于0，那么j需要左←移去更小的数
                else if (sum > 0) {
                    // 如j和j左面的数相同，就没有再去判断的必要了
                    while (i < j && nums[j] == nums[--j]) ;
                } else {
                    // 满足三数和为0,存放在结果集中
                    res.add(new ArrayList<Integer>(Arrays.asList(nums[k], nums[i], nums[j])));
                    // 可能存在多组解，同时去除重复接，并同时将 i，j移到下一位置，寻找新的解
                    while (i < j && nums[i] == nums[++i]) ;
                    while (i < j && nums[j] == nums[--j]) ;
                }
            }
        }
        return res;
    }


    /**
     * 超出时间限制，时间复杂度 O(n^2)
     * 双重暴力+hash
     */
    public static List<List<Integer>> threeSum1(int[] nums) {
        // 如果数组的长度小于2，一定没有满足条件的集合
        if (nums == null || nums.length <= 2) {
            return Collections.emptyList();
        }
        // 排序
        Arrays.sort(nums);

        // 使用Set防重，对结果防重
        Set<List<Integer>> result = new LinkedHashSet<>();

        // 遍历数组
        for (int i = 0; i < nums.length - 2; i++) {
            // 使用Hash表存储数据，
            Map<Integer, Integer> hashMap = new HashMap<>();
            for (int j = i + 1; j < nums.length; j++) {
                // 如果为没有两数之和等于第三个数的相反数，就不满足三数之和为0的条件
                if (hashMap.get(-nums[i] - nums[j]) != null) {
                    // 把满足条件数据生成集合
                    List<Integer> list = Arrays.asList(nums[i], hashMap.get(-nums[i] - nums[j]), nums[j]);
                    // 对集合进行排序，防止 [1,0,-1] [-1,0,1]去不掉
                    Collections.sort(list);
                    // 放入Set中，对结果进行去重
                    result.add(list);
                } else {
                    // 将不满足的条件的存储在hash表中（有可能是数据不够，或者没有满足条件的数据）
                    hashMap.put(nums[j], nums[j]);
                }
            }
        }
        // 转成集合返回
        return new ArrayList<>(result);
    }

    /**
     * 超出时间限制，时间复杂度 O(n^3)
     */
    public static List<List<Integer>> threeSum2(int[] nums) {
        // 如果数组的长度小于2，一定没有满足条件的集合
        if (nums == null || nums.length <= 2) {
            return Collections.emptyList();
        }
        // 排序
        // 使用Set防重，对结果防重
        Set<List<Integer>> result = new LinkedHashSet<>();
        // 三重for循环
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                for (int k = j + 1; k < nums.length; k++) {
                    // 如果满足三数和是0
                    if (nums[i] + nums[j] + nums[k] == 0) {
                        // 把满足条件数据生成集合
                        List<Integer> value = Arrays.asList(nums[i], nums[j], nums[k]);
                        // 放入Set中
                        result.add(value);
                    }
                }
            }
        }
        // 转成集合返回
        return new ArrayList<>(result);
    }
}

?