15. 三数之和

题目描述

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]

知识点

数组

Qiang的思路

对于这个问题，最先想到的思路是：设定三个指针，分别指向三个元素，然后对其进行求和判断，得到结果。但是这样做的时间复杂度太高了，是。所以对其进行改进。
具体改进措施：对于最外层循环不做处理，但是对于内两层循环，我们可以看出是对一个寻列求其中两个元素的和为某一固定值的元素对。这个任务可以通过两个指针实现，另外，预先对数组进行排序，便可以将两个指针同时从两头进行遍历，这样可以得到内层循环为时间复杂度的解题方式。
但是这样做还是存在着时间超时的问题，所以针对串的元素可重复特点，对重复元素进行特殊处理，这样便可以降低时间复杂度的系数，进而AC。

PS：特殊情况需要注意，当串的长度为0时直接返回空集合便可。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
        if(nums.size()==0)
           return result; 
        std::sort(nums.begin(), nums.end());
        for(int i=0; i<nums.size()-1;i++){
            for(int j=i+1, k=nums.size()-1; j<k; ){
                int flag=nums[i]+nums[j]+nums[k];
                if(flag==0)
                    result.push_back({nums[i], nums[j], nums[k]});
                if(flag<=0){
                    while(j<k && nums[j]==nums[j+1])
                        j++;
                    j++;
                }
                if(flag>=0){
                    while(j<k && nums[k]==nums[k-1])
                        k--;
                    k--;
                }
            }
            while(i<nums.size()-1 && nums[i]==nums[i+1])
                i++;
        }
        return result;
    }
};

作者原创，如需转载及其他问题请邮箱联系：lwqiang_chn@163.com。
个人网站：https://www.myqiang.top。