Time Limit Exceeded - using unordered_map in O(n^2)


  • 0
    Z
    /**************************hash_function***************************************/
    template <class T>
    inline void hash_combine(std::size_t& seed, const T& v)
    {
        hash<T> hasher;
        seed ^= hasher(v) + 0x9e3779b9 + (seed<<6) + (seed>>2);
    }
    
    template <typename Object>
    struct ObjectHasher
    {
        std::size_t operator()(const Object& k) const
        {
            std::size_t hash = 0;
            for (auto i=0; i<k.size(); i++){
                hash_combine(hash, k[i]);
            }
            return hash;
        }
    };
    /**************************hash_function***************************************/
    
    class Solution {
    public:
        vector<vector<int> > threeSum(vector<int> &num) {
            int target1, target2;
            vector<vector<int>> rtnNumlist; //vector should be vector<int>, not vector<int, int>
            unordered_map<vector<int>, int, ObjectHasher<vector<int>>> uset1; //avoid duplicate sets
            
            sort(num.begin(), num.end());
            
            for(int i=0; i<num.size(); i++){
                unordered_map<int, int> uset2; //initialize every time
                
                    target1=0-num[i];
                    for(int j=i+1; j<num.size(); j++){
                        if (j==i) {
                            continue;
                        }
                        else{
                            if(uset2.find(num[j])!=uset2.end()){ //here find(x), x should be the value not the target
                                vector<int> rtnNum;
                                rtnNum.push_back(num[i]);
                                int tmp=num[j]; //this part was confused. watch out which part is stored in the unordered_map
                                tmp=uset2[tmp];
                                rtnNum.push_back(num[tmp]);
                                rtnNum.push_back(num[j]);
                                sort(rtnNum.begin(), rtnNum.end());
                                if (uset1.find(rtnNum)!=uset1.end()) {
                                    continue;
                                }
                                else{
                                    rtnNumlist.push_back(rtnNum);
                                    uset1.insert(pair<vector<int>, int> (rtnNum, j));
                                }
                            }
                            else{
                                target2=target1-num[j];
                                uset2.insert(pair<int, int> (target2, j));
                            }
                        }
                    }
                
            }
            
            return rtnNumlist;
            
        }
    };

Log in to reply
 

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