题目:

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

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

 

示例:

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

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

解:这道题一开始的解法如下,讲其分为查找两数之和的子问题,但测试用例再最后两个用例上显示超时

class Solution1 { 
public: 
    vector<vector<int>> threeSum(vector<int>& nums) { 
    std::sort(nums.begin(),nums.end()); 
    vector<vector<int>> v2; 
    set<vector<int>>set_v2; 
    int i=0; 
    if(nums.size()<=2) 
    { 
        return v2; 
    } 
    for (;i<nums.size()-2;i++) 
    { 
        int tmp_1=nums[i]; 
        int j=i+1; 
        map<int,int> tmp_map; 
       //unordered_map<int,int> tmp_map;
        for(;j<nums.size();j++)         {             vector<int> vec_3;             int tmp_2=-tmp_1-nums[j];                          if(tmp_map.find(tmp_2)!=tmp_map.end())             {                 vec_3.push_back(tmp_1);                 vec_3.push_back(tmp_2);                 vec_3.push_back(nums[j]);                 sort(vec_3.begin(),vec_3.end());                 if(set_v2.find(vec_3)==set_v2.end())                 {                     set_v2.insert(vec_3);                     v2.push_back(vec_3);                 }             }             tmp_map[nums[j]]=j;                      }              }     return v2; } };
测试可得unordered_map的时间比map快一倍,unordered_map为4s,map为7s。且将tmp_map[nums[j]]=j;这行注释后,时间缩短为1s
可得插入时间比较费时
以上的时间复杂度计算为O(n2),但未计算map插入的时间复杂度,可能应该为O(n2*logn)
下面为双指针方法,时间复杂度O(N2),所有测试用例通过
class Solution { 
public: 
    vector<vector<int>> threeSum(vector<int>& nums) { 
        //排序的作用在于去掉重复的数字 
    std::sort(nums.begin(),nums.end()); 
    vector<vector<int>> v2; 
    int i=0; 
    //异常处理 
    if(nums.size()<=2) 
    { 
        return v2; 
    } 
    for (;i<nums.size();i++) 
    { 
        //大于0就不用往下走 
        if(nums[i]>0) 
        { 
            break; 
        } 
        if(i>0&&nums[i-1]==nums[i]) 
        { 
            continue; 
        } 
        int i_left=i+1; 
        int i_right=nums.size()-1; 
        while(i_left<i_right) 
        { 
            if(nums[i]+nums[i_left]+nums[i_right]==0) 
            { 
                v2.emplace_back(std::vector<int>({nums[i],nums[i_left],nums[i_right]})); 
                //寻找接下来满足条件的 
                //首先跳过重复的 
                while(i_left<i_right &&nums[i_left]==nums[i_left+1]) 
                    i_left++; 
                while(i_left<i_right &&nums[i_right]==nums[i_right-1]) 
                    i_right--;  
                i_left++; 
                i_right--; 
            } 
            else if(nums[i]+nums[i_left]+nums[i_right]>0) 
            { 
                i_right--; 
            } 
            else 
                i_left++; 
        } 
    } 
    return v2; 
} 
};
 

关于双指针方法,双指针的使用 一般要先进行排序

下面是别人对其进行的总结

https://www.cnblogs.com/codingstory/p/11334827.html

 

 

发布评论

分享到:

IT源码网

微信公众号号:IT虾米 (左侧二维码扫一扫)欢迎添加!

STL——萃取机制(Traits)讲解
你是第一个吃螃蟹的人
发表评论

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。