题解 | #三数之和#

题目主要信息:

• 给定一个长度为$nn$的数组，要找出其中所有满足相加等于0的三元组，即数组中所有三个相加为0的数集
• 三元组内部必须非降序排列，且三元组不能有重复

举一反三：

学习完本题的思路你可以解决如下题目：

BM50. 两数之和

哈希表（推荐使用）

知识点1：哈希表

哈希表是一种根据关键码（key）直接访问值（value）的一种数据结构。而这种直接访问意味着只要知道key就能在$O(1)O(1)$时间内得到value，因此哈希表常用来统计频率、快速检验某个元素是否出现过等。

知识点2：双指针

双指针指的是在遍历对象的过程中，不是普通的使用单个指针进行访问，而是使用两个指针（特殊情况甚至可以多个），两个指针或是同方向访问两个链表、或是同方向访问一个链表（快慢指针）、或是相反方向扫描（对撞指针），从而达到我们需要的目的。

思路：

直接找三个数字之和为某个数，太麻烦了，我们是不是可以拆分一下：如果找到了某个数$aa$，要找到与之对应的另外两个数，三数之和为0，那岂不是只要找到另外两个数之和为$-a-a$？这就方便很多了。

因为三元组内部必须是有序的，因此可以优先对原数组排序，这样每次取到一个最小的数为$aa$，只需要在后续数组中找到两个之和为$-a-a$就可以了，我们可以用双指针缩小区间，因为太后面的数字太大了，就不可能为$-a-a$，可以舍弃。

具体做法：

• step 1：排除边界特殊情况。
• step 2：既然三元组内部要求非降序排列，那我们先得把这个无序的数组搞有序了，使用sort函数优先对其排序。
• step 3：得到有序数组后，遍历该数组，对于每个遍历到的元素假设它是三元组中最小的一个，那么另外两个一定在后面。
• step 4：需要三个数相加为0，则另外两个数相加应该为上述第一个数的相反数，我们可以利用双指针在剩余的子数组中找有没有这样的数对。双指针指向剩余子数组的首尾，如果二者相加为目标值，那么可以记录，而且二者中间的数字相加可能还会有。
• step 5：如果二者相加大于目标值，说明右指针太大了，那就将其左移缩小，相反如果二者相加小于目标值，说明左指针太小了，将其右移扩大，直到两指针相遇，剩余子数组找完了。

注：对于三个数字都要判断是否相邻有重复的情况，要去重。

图示：

Java实现代码：

import java.util.*;
public class Solution {
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        ArrayList<ArrayList<Integer> > res = new ArrayList<ArrayList<Integer>>();
        int n = num.length;
        //不够三元组
        if(n < 3) 
            return res;
        //排序
        Arrays.sort(num); 
        for(int i = 0; i < n - 2; i++){
            if(i != 0 && num[i] == num[i - 1])
                continue;
            //后续的收尾双指针
            int left = i + 1; 
            int right = n - 1;
            //设置当前数的负值为目标
            int target = -num[i]; 
            while(left < right){
                //双指针指向的二值相加为目标，则可以与num[i]组成0
                if(num[left] + num[right] == target){
                    ArrayList<Integer> temp = new ArrayList<Integer>();
                    temp.add(num[i]);
                    temp.add(num[left]);
                    temp.add(num[right]);
                    res.add(temp);
                    while(left + 1 < right && num[left] == num[left + 1])
                        //去重
                        left++; 
                    while(right - 1 > left && num[right] == num[right - 1])
                        //去重
                        right--; 
                    //双指针向中间收缩
                    left++; 
                    right--;
                }
                //双指针指向的二值相加大于目标，右指针向左
                else if(num[left] + num[right] > target)
                    right--;
                //双指针指向的二值相加小于目标，左指针向右
                else 
                    left++;
            }
        }
        return res;
    }
}

C++实现代码：

class Solution {
public:
    vector<vector<int> > threeSum(vector<int> &num) {
        vector<vector<int> > res;
        int n = num.size();
        //不够三元组
        if(n < 3) 
            return res;
        //排序
        sort(num.begin(), num.end()); 
        for(int i = 0; i < n - 2; i++){
            if(i != 0 && num[i] == num[i - 1])
                continue;
            //后续的收尾双指针
            int left = i + 1; 
            int right = n - 1;
            //设置当前数的负值为目标
            int target = -num[i]; 
            while(left < right){
                //双指针指向的二值相加为目标，则可以与num[i]组成0
                if(num[left] + num[right] == target){
                    res.push_back({num[i], num[left], num[right]});
                    while(left + 1 < right && num[left] == num[left + 1])
                        //去重
                        left++; 
                    while(right - 1 > left && num[right] == num[right - 1])
                        //去重
                        right--; 
                    //双指针向中间收缩
                    left++; 
                    right--;
                }
                //双指针指向的二值相加大于目标，右指针向左
                else if(num[left] + num[right] > target)
                    right--;
                //双指针指向的二值相加小于目标，左指针向右
                else 
                    left++;
            }
        }
        return res;
    }
};

Python实现代码：

class Solution:
    def threeSum(self , num: List[int]) -> List[List[int]]:
        res = list(list())
        n = len(num)
        #不够三元组
        if n < 3: 
            return res
        #排序
        num.sort() 
        for i in range(n - 2):
            if i != 0 and num[i] == num[i - 1]:
                continue
            #后续的收尾双指针
            left = i + 1 
            right = n - 1
            #设置当前数的负值为目标
            target = -num[i] 
            while left < right:
                #双指针指向的二值相加为目标，则可以与num[i]组成0
                if num[left] + num[right] == target: 
                    res.append([num[i], num[left], num[right]])
                    while left + 1 < right and num[left] == num[left + 1]:
                        #去重
                        left += 1 
                    while right - 1 > left and num[right] == num[right - 1]:
                        #去重
                        right -= 1 
                    #双指针向中间收缩
                    left += 1 
                    right -= 1
                #双指针指向的二值相加大于目标，右指针向左
                elif num[left] + num[right] > target: 
                    right -= 1
                #双指针指向的二值相加小于目标，左指针向右
                else: 
                    left += 1 
        return res

复杂度分析：

• 时间复杂度：$O(n^2)O(n^2)$，排序的复杂度为$O(nlo{g}_{2}n)O(nlog\_2n)$，查找三元组的复杂度为$O(n^2)O(n^2)$
• 空间复杂度：$O(1)O(1)$，res属于必要空间，不属于额外空间，无其他辅助空间