Please help!! Why it is "time limit exceeded" on this 4Sum problem?


  • 1
    I
    class Solution {
    public:
        vector<vector<int> > fourSum(vector<int> &num, int target) {
            vector<vector<int>> rt;
            set<vector<int>> mset;
            int n = num.size();
            if (n<4) return rt;
            unordered_map<int, vector<vector<int>> > hm;
    
            
            for (int i = 0; i<n-1; i++) {
                for (int j=i+1; j<n; j++) {
                    vector<int> v;
                    v.push_back(i);
                    v.push_back(j);
                    
                    unordered_map<int, vector<vector<int>>>::iterator mate = hm.find(target- (num[i]+num[j])); 
                    if (mate!=hm.end()) {
                        for ( vector<vector<int>>::iterator it2 = (mate->second).begin(); it2 != (mate->second).end(); it2++) {
                            if ( i!=(*it2)[0] && j!=(*it2)[0] && i!=(*it2)[1] && j!=(*it2)[1] ) {
                                vector<int> vt2;
                                vt2.push_back(num[i]);
                                vt2.push_back(num[j]);
                                vt2.push_back(num[(*it2)[0]]);
                                vt2.push_back(num[(*it2)[1]]);
                                sort(vt2.begin(), vt2.end());
                                mset.insert(vt2);
                            }
                        }
                    }
                    (hm[num[i]+num[j]]).push_back(v);
                }
            }
            
            for (auto it3=mset.begin(); it3!=mset.end(); it3++) {
                rt.push_back(*it3);
            }
            
            return rt;
        }
        
    };

  • 2
    H

    i write similar code and got TLE too. i tested the case on my laptop and only found it run 36ms. How STRANGE!


  • 0
    S

    I got TLE too......I can't understand why at all ..........


  • 0
    L

    Probably the problem is with STL set and map..they have large constants in complexity.. using hashing may help


Log in to reply
 

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