Different outputs from local machine and the OJ


  • 1
    H

    My code generates different result on the OJ and local machine for the input { 5, 0, 1, 1, -2, -1, -2 }, the expected result would be [[-2, -2, -1, 0]], which is exactly the one that my local machine output, but when I submit the code to the OJ, it output [] (empty set). I have no idea why, I'll be very appreciate if some one would help with this. The code snippet is as following:

    class Solution {
    public:
    vector<vector<int> > fourSum(vector<int> &num, int target) {
    	vector<vector<int> > ret;
    	if (4 > num.size()) return ret;
    
    	unordered_map<int, vector<pair<int, int> > > h;
    	int val;
    	sort(num.begin(), num.end());
    	
    	//generate all possible combinations of two number pairs
    	//and save their values (sums) and index combination
    	for (int i = 0; i < num.size() - 1; ++i)
    	{
    		for (int j = i + 1; j < num.size(); ++j)
    		{
    			//save their values (sums) and index combination
    			val = num[i] + num[j];
    			if (h.end() == h.find(val))
    			{		
    				//if the sum of the two value not found, create one
    				vector<pair<int, int> > s;	
    				s.push_back(make_pair(i, j));	
    				h.insert(make_pair(val, s));
    			}
    			else
    				h.at(val).push_back(make_pair(i, j));
    		}
    	}
    
    	int i = 0, c = (h.size() + 1) / 2; //iterates half of the sequence will be enough
    	vector<int> cand;
    	for (auto it = h.begin(), itp = h.end(); i <= c && it != h.end(); ++i, ++it)
    	{
    		//for each possible two-number combination, check if we could find another pair 
    		//of the two-number combination in the map that sum up to 'target',
    		if (h.end() == (itp = h.find(target - it->first))) continue;
    
    		//if we could find one, generates the 4 number sequences in non-descendent order
    		for (auto s : it->second)
    		{
    			for (auto y : itp->second)
    			{
    				if (s.first == y.first || s.first == y.second ||
    					s.second == y.first || s.second == y.second) continue;
    				cand.clear();
    				cand.push_back(num[s.first]);
    				cand.push_back(num[s.second]);
    				cand.push_back(num[y.first]);
    				cand.push_back(num[y.second]);
    				sort(cand.begin(), cand.end());
    				ret.push_back(cand);
    			}
    		}
    	}
    
    	//sort the 4-number sequence array
    	sort(ret.begin(), ret.end(), [](const vector<int> &lhs, const vector<int> &rhs) -> bool {
    		for (int i = 0; i < 4; ++i)
    		{
    			if (lhs[i] == rhs[i]) continue;
    			return lhs[i] < rhs[i];
    		}
    		return false;
    
    	});
    	//remove all duplicated ones
    	vector<vector<int> >::iterator itvv = unique(ret.begin(), ret.end(),
    		[](const vector<int> &lhs, const vector<int> &rhs) -> bool {
    		for (int i = 0; i < 4; ++i)
    		{
    			if (lhs[i] == rhs[i]) continue;
    			return false;
    		}
    		return true;
    	});
    	ret.erase(itvv, ret.end());
    	return ret;
    }
    

    };


  • 0
    Q

    // I have the similar problem. I compile it in Visual Studio 2013. I don't know why.
    class Solution {
    public:
    vector<vector<int> > fourSum(vector<int> &num, int target) {
    sort(num.begin(), num.end());
    unordered_multimap<int, pair<int, int> > myht;
    vector<vector<int> > output;
    for (int i = 0; i<num.size(); i++)
    for (int j = i + 1; j<num.size(); j++)
    myht.insert(make_pair(num[i] + num[j], make_pair(i, j)));

    	for (int i = 0; i < myht.bucket_count(); i++)
    	{
    		int m = -1, n = -1;
    		for (auto itr = myht.begin(i); itr != myht.end(i); itr++)
    		{
    			if (m == -1 && n == -1)
    			{
    				m = itr->second.first;
    				n = itr->second.second;
    			}
    			else
    			{
    				if (num[m] == num[itr->second.first] && num[n] == num[itr->second.second])
    					continue;
    				else
    				{
    					m = itr->second.first;
    					n = itr->second.second;
    				}
    			}
    
    			int sum1 = itr->first;
    			auto range = myht.equal_range(target - sum1);
    			int p1 = -1, p2 = -1;
    			for (auto itr2 = range.first; itr2 != range.second; ++itr2)
    			{
    				if (!(itr2->second.first > itr->second.second))
    					continue;
    				if (p1 == -1 && p2 == -1)
    				{
    					p1 = itr2->second.first;
    					p2 = itr2->second.second;
    				}
    				else
    				{
    					if (num[p1] == num[itr2->second.first] && num[p2] == num[itr2->second.second])
    						continue;
    					else
    					{
    						p1 = itr2->second.first;
    						p2 = itr2->second.second;
    					}
    				}
    				output.push_back({ num[itr->second.first], num[itr->second.second], num[itr2->second.first], num[itr2->second.second] });
    			}
    		}
    	}
    
    	return output;
    }
    

    };


  • 0
    H

    I've found the problem of my code. At the very beginning, I thought that when searching through the counter part of an element in the two-sum sequence, iterates half of the sequence would be enough, but it is dead wrong, because the possible answer may have both two-sum number locate in the second half on the sequence, so I have to search through the whole sequence instead half of them. Here's my modified ac solution, hope this may help:

    class Solution {
    public:
    vector<vector<int> > fourSum(vector<int> &num, int target) {
    vector<vector<int> > ret;
    if (num.size() < 4) return ret;
    sort(num.begin(), num.end());
    pair<int, int> p;
    unordered_map<long long, set<pair<int, int> > > pairSums;
    vector<int> possibleAns;
    int i, j, sum;
    unordered_map<long long, set<pair<int, int> > >::iterator it, it1;
    set<pair<int, int> >::iterator itMS, itMS1;
    unordered_map<int, int> numcnt;

    	for (i = 0; i < num.size(); ++i)
    	{
    		if (numcnt.find(num[i]) == numcnt.end())
    			numcnt.insert(make_pair(num[i], 1));
    		else ++numcnt[num[i]];
    	}
    
    	for (i = 0; i < num.size(); ++i)
    	{
    		for (j = i + 1; j < num.size(); ++j)
    		{
    			sum = num[i] + num[j];
    			p.first = num[i];
    			p.second = num[j];
    			if ((it = pairSums.find(sum)) == pairSums.end())
    			{
    				pairSums.insert(make_pair(sum, set<pair<int, int> >()));
    				it = pairSums.find(sum);
    			}
    			it->second.insert(p);
    		}
    	}
    	for (it = pairSums.begin(); it != pairSums.end(); ++it)
    	{
    		if ((it1 = pairSums.find(target - it->first)) != pairSums.end())
    		{
    			for (auto x : it1->second)
    				for (auto y : it->second)
    				{						
    					--numcnt[x.first];
    					--numcnt[x.second];
    					--numcnt[y.first];
    					--numcnt[y.second];
    					if (numcnt[x.first] >= 0 && numcnt[x.second] >= 0 &&
    						numcnt[y.first] >= 0 && numcnt[y.second] >= 0)
    					{
    						possibleAns.clear();
    						possibleAns.push_back(x.first);
    						possibleAns.push_back(x.second);
    						possibleAns.push_back(y.first);
    						possibleAns.push_back(y.second);
    						sort(possibleAns.begin(), possibleAns.end());
    						ret.push_back(possibleAns);
    					}
    					++numcnt[x.first];
    					++numcnt[x.second];
    					++numcnt[y.first];
    					++numcnt[y.second];
    				}
    		}
    	}
    
        int count = ret.size();
        if (count > 0) possibleAns = ret[0];
    	sort(ret.begin(), ret.end(), [](vector<int> const &a, vector<int> const &b) -> bool {
    		for (int i = 0; i < 4; ++i)
    			if (a[i] != b[i]) return a[i] < b[i];
    		return a[3] < b[3];
    	});
    	vector<vector<int> >::iterator itV = unique(ret.begin(), ret.end(),
    		[](vector<int> const &a, vector<int> const &b) -> bool {
    		for (int i = 0; i < 4; ++i)
    			if (a[i] != b[i]) return false;
    		return true;
    	});
    	
    	ret.resize(distance(ret.begin(), itV));
    	if (ret.size() == 0 && count > 0) ret.push_back(possibleAns); 
    	return ret;
    }
    

    };


Log in to reply
 

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