AC in 300ms, but not satisfied with my solution, strongly hope to be optimized.


  • 0
    H

    I use std::set to sort and count each number. And then delete excess zero, then calculate sum of each pair, include the element appears twice, and record the smaller one in the pair by hash. then traverse all elements A in std::set, search -1*value in the hash table, and output the smaller one which is >= A. Here is my code, it is kind of mess.

    class Solution {
    public:
        vector<vector<int> > threeSum(vector<int> &num) {
    		map<int, int> mnum;
    		map<int, vector<int>> mrec;
    		vector<vector<int> > ret;
    		for(int i = 0; i < num.size(); i ++)
    			mnum[num[i]] ++;
    		if(mnum.find(0) != mnum.end())
    		{
    			if(mnum[0] >= 3)
    				ret.push_back(vector<int>(3,0));
    			mnum[0] = 1;
    		}
    		for(auto it1 = mnum.begin(); it1 != mnum.end(); ++ it1)
    		{
    			auto it2 = it1;
    			if(it1->second > 1)
    				mrec[2*it1->first].push_back(it1->first);
    			while(true)
    			{
    				it2 ++;
    				if(it2 == mnum.end())
    					break;
    				mrec[it1->first+it2->first].push_back(it1->first);
    			}
    		}
    		for(auto it = mnum.begin(); it != mnum.end(); ++ it)
    		{
    			auto it2 = mrec.find(it->first*(-1));
    			if(it2 != mrec.end())
    			{
    				for(int i = it2->second.size()-1; i >=0; i --)
    				{
    					if(it->first < it2->second[i])
    					{
    					    vector<int> row;
    						row.push_back(it->first);
    						row.push_back(it2->second[i]);
    						row.push_back(0 - it->first - it2->second[i]);
    						ret.push_back(row);
    					}
    					else if(it->first == it2->second[i])
    					{
    						if(mnum[it->first] > 1)
    						{
    						    vector<int> row;
    							row.push_back(it->first);
    							row.push_back(it->first);
    							row.push_back(0 - it->first - it->first);
    							ret.push_back(row);
    						}
    					}
    					else
    					    break;
    				}
    			}
    		}
            return ret;
        }
    };

  • 1
    S

    Hopefully, this post will give you some hint.


  • 0
    H

    Thank you, that is very useful!!!!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.