题目主要信息:

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

具体思路:

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

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

具体过程如下图所示: alt

代码实现:

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){
                if(num[left] + num[right] == target){//双指针指向的二值相加为目标,则可以与num[i]组成0
                    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;
    }
};

复杂度分析:

  • 时间复杂度:O(n2)O(n^2),排序的复杂度为O(nlog2n)O(nlog_2n),查找三元组的复杂度为O(n2)O(n^2)
  • 空间复杂度:O(1)O(1),res属于必要空间,不属于额外空间