Different outputs from local machine and OJ


  • 1
    J

    The input is [2,1,0,-1], 2. My local machine output [[-1,0,1,2]], but OJ generates an empty vector. It's strange!

    typedef vector<pair<int,int> > VP; 
    typedef pair<int,int> PII; 
    
    vector<vector<int> > fourSum(vector<int> &num, int target) {
        sort(num.begin(),num.end());
        int len = num.size(); 
        unordered_map<int,VP> dict; 
        for(int i = 0; i < len-1 ; i ++)
            for(int j = i+1; j < len ; j++)
                dict[num[i]+num[j]].push_back(pair<int,int>(i,j));
        vector<vector<int> > res; 
        unordered_map<int,VP>::iterator pos = dict.begin(); 
        while(pos != dict.end()){
            int s1 = pos->first; 
            int s2 = target-s1;
            if(s1 > s2)
                break;
            ++pos; 
            if(dict.find(s2) != dict.end()){
                VP p1 = dict[s1]; 
                VP p2 = dict[s2]; 
                for(int i = 0; i < p1.size(); i ++)
                    for(int j = 0; j < p2.size(); j++){
                        PII pi1 = p1[i]; 
                        PII pi2 = p2[j];
                        int i1 = pi1.first; int i2 = pi1.second; 
                        int j1 = pi2.first; int j2 = pi2.second; 
                        if(i1 != j1 && i1 != j2 && i2 != j1 && i2 != j2){
                            vector<int> temp; 
                            temp.push_back(num[i1]); temp.push_back(num[i2]); temp.push_back(num[j1]); temp.push_back(num[j2]);
                            sort(temp.begin(),temp.end()); 
                            res.insert(temp);
                        }
                    }
            }
        }
        sort(res.begin(),res.end()); 
        vector<vector<int>>::iterator iter = unique(res.begin(),res.end()); 
        res.resize(distance(res.begin(),iter));
        return res;
    }

  • 5
    0

    I test your code in my computer, and it fails. The result is empty because if(s1 > s2) is true in the first time of the loop,
    The sentence below is quoted form cpluscplus:

    Notice that an unordered_map object makes no guarantees on which
    specific element is considered its first element.
    Because of this, you cannot use if(s1 > s2) b break;to stop the loop.


  • 0
    J

    thanks a lot!


  • 0
    S

    dict[num[i]+num[j]].push_back(pair<int,int>(i,j));

    Could you elaborate this statement? I understand that you are finding the pair(i,j) that gives a particular sum and store that pair as the value for that key. What if there are 2 pairs whose sum gives the same index? i.e; 0+4 and 1+3, for instance? Basically, how are duplicates dealt with?


Log in to reply
 

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