leetcode(力扣)第十五题：三数之和_C++

本文主要是介绍leetcode(力扣)第十五题：三数之和_C++，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        unordered_map<int, int> nums_map;//哈希表
        int si=nums.size(),ptr1=0,ptr2=si-1,t=0;//前后指针和第三个数
        vector<vector<int>> ans;//答案
        if(si<3) return ans;

        sort(nums.begin(), nums.end());//排序
        for(int i=0;i<=ptr2;i++){//做哈希表
            auto it=nums_map.find(nums[i]);
            if(it!=nums_map.end()) ++(it->second);
            else nums_map[nums[i]]=1;
        }
        while(ptr1<si-2&&nums[ptr1]==nums[ptr1+1]) ++ptr1;
        while(ptr2>1&&nums[ptr2]==nums[ptr2-1]) --ptr2;
        
        if(nums_map.find(0)!=nums_map.end()&&nums_map[0]>2) ans.push_back({0,0,0});
        while(1){
            if(ptr2-ptr1<1||(nums[ptr1]^nums[ptr2])>0) break;
            while(1){
                t=0-nums[ptr1]-nums[ptr2];
                if(ptr2-ptr1<1) break;
                if(nums[ptr1]>t||t>nums[ptr2]);
                else if(nums[ptr1]==t||nums[ptr2]==t){
                    if(nums_map[t]>1) ans.push_back({t,t,-2*t});
                }    
                else if(nums_map.find(t)!=nums_map.end())
                    ans.push_back({nums[ptr1],t,nums[ptr2]});
                ++ptr1;
                while(ptr1<si-2&&nums[ptr1]==nums[ptr1+1]) ++ptr1;
            }
            ptr1=0;
            while(ptr1<si-2&&nums[ptr1]==nums[ptr1+1]) ++ptr1;
            --ptr2;
            while(ptr2>1&&nums[ptr2]==nums[ptr2-1]) --ptr2;
        }
        return ans;
    }
};

本解法专为大量数据而生。（确信）
暴力求解时间复杂度为O(N^3)，很不行，通过双指针+哈希表+分支限界可以把情况调整到O(N*N)以下。但是面对少量数据是真的很不好啊（悲
先排序（这里使用的是快排），再做哈希表nums_map，nums_map存储的数是每个数字的个数。

先寻找是否有三个0.有则输出。

剩下的采用双指针，一个指针指向最小数的最后一个，一个指针指向最大数的第一个。
对它们进行双重遍历。第一重后指针往前，第二重前指针往后。
第一重每个循环后指针指向数的第一个，第二重每个循环前指正指向数的最后一个。
循环中，在两个指针中寻找第三个数，要求第前指针数<第三个数<后指针数。
外循环有两种情况能直接break:后指针-前指针<1;前指针数*后指针数>=0。
内循环有三种情况能直接break:后指针-前指针<1;前指针数>=第三个数;第三个数>=后指针数。

寻找两个相同的数需要一次遍历0以外的数组元素然后找nums_map，nums_map[nums[i]]>1就输出。

f(后指针-前指针<1||前指针数>第三个数||第三个数>后指针数) break;
if(前指针数第三个数&&nums_map[前指针数]>1) 输出
else if(后指针数第三个数&&nums_map[后指针数]>1) 输出；
else if(nums_map[0-nums[ptr1]-nums[ptr2]] exit) 输出；
由于后指针-前指针<=1先break，因此不会同时满足前指针数第三个数&&后指针数第三个数。

这篇关于leetcode(力扣)第十五题：三数之和_C++的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！