文章收录于LeetCode专栏

---

三数之和

  给你一个包含n个整数的数组nums，判断nums中是否存在三个元素a、b、c ，并使得a + b + c = 0 ？请你找出所有和为0且不重复的三元组。
  注意：答案中不可以包含重复的三元组。
  示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

  示例 2：

输入：nums = []
输出：[]

  示例 3：

输入：nums = [0]
输出：[]

题解

  第一步审题，给定一个数组请求其中任意不重复三个元素之和为0，题意很简单就是任意从数组中取三个元素相加要等于0，且求出所有不重复的组合。
  第二步列出所有解，首先可以使用暴力三层枚举求解，其次在两数之和基础之上使用一个hash表来换取少一层循环，最后可以使用双指针左右夹逼法来求解。

解法一（暴力枚举）

  所谓暴力枚举就是采用三层循环，每层循环取出数组中一个元素，判断三层循环取出的三个元素相加是否等于0，因为要求不包含重复的三元组，所以在判断的过程中必须要进行一次判重。

class Solution{
    public List<List<Integer>> threeSum(int[] nums){
        if(nums.length == 0){
            return Collections.emptyList();
        }
        Set<List<Integer>> res = new HashSet<>();
        for(int i=0; i<nums.length-2; i++){
            for(int j=i+1; j<nums.length-1; j++){
                for(int k=j+1; k<nums.length; k++){
                    if(nums[i] + nums[j] + nums[k] == 0){
                        List<Integer> list = Arrays.asList(nums[i], nums[j], nums[k]);
                        Collections.sort(list);
                        res.add(list);
                    }
                }
            }
        }
        return new ArrayList(res);
    }
}

解法二（hash表）

  在求解两数之和的时候使用空间换时间的方式，采用hash表来记录遍历到的元素，从而可以用于下次判断的时候使用，同样三数之和也可以使用hash表来记录一层元素，使其退化为两数之和，只是这里的目标值每次都不一样而已，同样需要对结果进行判重操作。

class Solution{
    public List<List<Integer>> threeSum(int[] nums){
        if(nums.length == 0){
            return Collections.emptyList();
        }
        Set<List<Integer>> res = new HashSet<>();
        for(int i=0; i<nums.length-1; i++){
            int target = 0 - nums[i];
            Map<Integer, Integer> map = new HashMap<>();
            for(int j=i+1; j<nums.length; j++){
                int sub = target - nums[j];
                if(Objects.nonNull(map.get(sub))){
                    List<Integer> list = Arrays.asList(nums[j], sub, nums[i]);
                    Collections.sort(list);
                    res.add(list);
                }
                map.put(nums[j], j);
            }
        }
        return new ArrayList(res);
    }
}

解法三（左右指针夹逼）

  以上两种解法因为它们消耗的时间都太高，所以表现都不尽人意。题目中没有要求元素下标，所以我们完全可以先将数组进行从小到大排序，这样一来我们就可以从左开始每次固定一个元素，再使用左右两个指针来移动获取剩下的两个元素，如果当前三数之和小于0，则说明左指针应该向右移动（已经对数组进行排序，右边元素大于左边元素）；如果当前三数之和大于0，则说明右指针应该向左移动；等于0则说明找到匹配元组。

class Solution{
    public List<List<Integer>> threeSum(int[] nums){
        if(nums.length == 0){
            return Collections.emptyList();
        }
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        for(int i=0; i<nums.length-2; i++){
            if(nums[i] > 0){
                // 当元素大于0，说明以后元素都大于0，三数之和不可能再为0
                break;
            }
            if(i > 0 && nums[i] == nums[i-1]){
                // 跳过重复元素
                continue;
            }
            // 左指针
            int j = i + 1;
            // 右指针
            int k = nums.length -1;
            while(j < k){
                int sum = nums[i] + nums[j] + nums[k];
                if(sum == 0){
                    res.add(Arrays.asList(nums[i], nums[j], nums[k]));
                    // 跳过重复元素
                    while(j < k && nums[j] == nums[++j]);
                    // 跳过重复元素
                    while(j < k && nums[k] == nums[--k]);
                }
                if(sum < 0){
                    // 三数之和小于0，左指针向右移动
                    // nums[j] == nums[++j] 移动且跳过重复元素
                    while(j < k && nums[j] == nums[++j]);
                }
                if(sum > 0){
                    // 三数之和大于0，右指针向左移动
                    // nums[k] == nums[--k] 移动且跳过重复元素
                    while(j < k && nums[k] == nums[--k]);
                }
            }
        }
        return res;
    }
}

  第三步分析时间复杂度和空间复杂度，暴力枚举法使用了三层循环且没有使用额外的内存空间，所以时间复杂度为O(n³)，空间复杂度为O(1)；hash表使用空间换时间的方法，所以时间复杂度为O(n²)，空间复杂度为O(n)；左右指针夹逼同样使用了两层循环所以时间复杂度为O(n²)，但是没有使用额外的内存空间所以空间复杂度为O(n)。

---

一键三连，让我的信心像气球一样膨胀！