【LeetCode】三数之和【排序，固定一个数，然后双指针寻找另外两个数】

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/3sum

分析：

暴力法的复杂度是O(N^3),肯定会超时

先将数组排序，假设k1<=k2<=k3,先固定k1,然后通过双指针法在k1的后面寻找k2和k3

可以利用的性质：

1.如果k1大于0，则三数之和肯定无法等于0，可以跳过该k1

2.如果v[i]==v[i-1]，那么i-1可以跳过，因为这样必然会导致重复结果

可以采用set去除重复结果

时间复杂度：O(N^2)

排序的复杂度是O(N*log N),但是后续固定看+双指针的复杂度是O(N^2),二者取大的，所以时间复杂度是O(N^2)

空间复杂度：快排需要，最好情况：O(log N),最坏情况：O(N)

code：

class Solution {

public:

vector<vector<int> > threeSum(vector<int>& a)

{

    vector<vector<int> > vv;

    vector<int> v;

    set<vector<int> > s;

    set<vector<int> >::iterator it;

    int n=a.size();

    if(n<)

        return vv;

    sort(a.begin(),a.end());

    for(int k=;k<n-;k++)

    {

        if(a[k]>)

            continue;

        if(k>&&a[k-]==a[k])

            continue;

        int l=k+;

        int h=n-;

        //cout<<"k="<<k<<"l="<<l<<" h="<<h<<endl;

        s.clear();

        while(l<h)

        {

            int ans=a[k]+a[l]+a[h];

            //cout<<"l="<<l<<" h="<<h<<"ans="<<ans<<endl;

            if(ans==)

            {

                v.clear();

                v.push_back(a[k]);

                v.push_back(a[l]);

                v.push_back(a[h]);

                s.insert(v);

                l++;

                h--;

            }else if(ans<)

            {

                l++;

            }else if(ans>)

            {

                h--;

            }

        }

        if(s.size()!=)

        {

            for(it=s.begin();it!=s.end();it++)

            {

                vv.push_back(*it);

            }

        }

    }

    return vv;

}

};

巴特西

【LeetCode】三数之和【排序，固定一个数，然后双指针寻找另外两个数】

最新文章

热门文章