2.三数之和(题号：15)

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

public class ThreeSum {
    //测试
    public static void main(String[] args) {
        int[] input = {-1, 0, 1, 2, -1, -4};

        ThreeSum threeSum = new ThreeSum();

        System.out.println(threeSum.threeSum3(input));

    }
    /**
     * 方法一：暴力破解  未去重
     * @param nums
     * @return
     */
    public List<List<Integer>> threeSum(int[] nums) {
        int n = nums.length;
        //定义结果列表
        List<List<Integer>> result = new ArrayList<>();

        //三重for循环 枚举所有的三数组合
        for (int i = 0; i < n-2; i++) {
            for (int j = i+1; j <n-1 ; j++) {
                for (int k = j+1; k < n; k++) {
                    if(nums[i]+nums[j]+nums[k]==0){
                        result.add(Arrays.asList(nums[i],nums[j],nums[k]));
                    }
                }
            }
        }
        return  result;
    }

    /**
     * 方法二：使用哈希表保存结果  未去重
     * @param nums
     * @return
     */
    public List<List<Integer>> threeSum2(int[] nums){
        int n = nums.length;

        List<List<Integer>> result = new ArrayList<>();

        // 定义一个hash map
        HashMap<Integer, List<Integer>> map = new HashMap<>();

        // 遍历数组，寻找每个数对应的那个数
        for( int i = 0; i < n; i++ ){
            int thatNum = 0 - nums[i];
            if (map.containsKey(thatNum)){
                // 如果已经存在thatNum，就找到了一组解
                ArrayList<Integer> tempList = new ArrayList<>(map.get(thatNum));
                tempList.add(nums[i]);
                result.add(tempList);
            }

            // 把当前数对应的两数组合都保存到map里
            for (int j = 0; j < i; j++ ){
                // 以两数之和作为key
                int newKey = nums[i] + nums[j];
                // 如果key不存在，就直接添加进去
                if (!map.containsKey(newKey)){
                    ArrayList<Integer> tempList = new ArrayList<>();
                    tempList.add(nums[i]);
                    tempList.add(nums[j]);
                    map.put( newKey, tempList );
                }
            }
        }
        return result;
    }

    /**
     * 方法三：双指针法
     * @param nums
     * @return
     */
    public List<List<Integer>> threeSum3(int[] nums) {
        int n = nums.length;
        //定义结果列表
        List<List<Integer>> result = new ArrayList<>();

        //1.先对数组进行排序
        Arrays.sort(nums);  //O(nlog(n))

        //2.遍历每一个元素，作为当前三元组中最小的，定义左右指针  时间复杂度O(n^2)
        for (int i = 0; i < n; i++) {
            //2.1 如果当前最小元素大于0，直接退出循环
            if(nums[i]>0)break;

            //2.2 如果当前数出现过，pass
            if(i>0&&nums[i]==nums[i-1]) continue;

            //2.3 定义左右指针
            int lp = i+1;
            int rp = n-1;

            //2.4 只要左指针保持小于右指针 继续移动指针
            while (lp<rp){
                int sum = nums[i]+nums[lp]+nums[rp];
                //判断sum的值，和0进行比较
                if(sum==0){
                    //2.4.1 sum==0 满足条件
                    result.add(Arrays.asList(nums[i],nums[lp],nums[rp]));
                    //左指针右移 右指针左移
                    lp++;
                    rp--;
                    //如果移动后的元素相同 直接跳过
                    while (lp<rp&&nums[lp]==nums[lp-1])lp++;
                    while (lp<rp&&nums[rp]==nums[rp+1])rp--;
                }else if(sum<0){
                    //2.4.2 小了  故左指针右移
                    lp++;
                }else {
                    //2.4.3 大了  故右指针左移
                    rp--;
                }
            }
        }
        return  result;
    }
}