Why this hashing solution keeps TLE?


  • 0
    I
    #include <utility>
    #include <unordered_map>
    class Solution {
    public:
        vector<vector<int> > fourSum(vector<int> &num, int target) {
            vector<vector<int> > result;
            // if the num's size is less than 4, clearly we should return
            if (num.size() < 4)
                return result;
            // mip stores values pairs
            unordered_map<int, vector<pair<int, int> > > mip;
            // isSearched stores whether a given value has been searched or not
            unordered_map<int, bool> isSearched; 
    
            // for any num[i], num[j], hash it into mip
            // key: num[i]+num[j]
            // value: a vector storing pair(i, j)
            for (int i{0}; i < num.size(); ++i) {
                for (int j{i+1}; j < num.size(); ++j) {
                    mip[num[i]+num[j]].push_back(make_pair(i, j));
                }
            }
    
            // loop against mip
            for (auto &kv: mip) {
                // fst_half: the sum of two numbers
                int fst_half{kv.first};
                // snd_half: the sum of another two numbers
                // fst_half + snd_half == target
                int snd_half{target-kv.first};
                // if already searched, we continue
                if (isSearched[fst_half] || isSearched[snd_half])
                    continue;
                isSearched[fst_half] = isSearched[snd_half] = true;
                if (mip[snd_half].size() != 0) {
                    // we take one pair from mip[fst_half].second and one pair from mip[snd_half].second
                    // and combine them together
                    for (size_t i{0}, j{0}; i < kv.second.size(); ++i) {
                        // if fst_half == snd_half, we set j = i+1 to eliminate seemingly duplication
                        if (fst_half == snd_half)
                            j = i+1;
                        else
                            j = 0;
                        for ( ; j < mip[snd_half].size(); ++j) {
                            int posa{kv.second[i].first}, posb{kv.second[i].second}, \
                                posc{mip[snd_half][j].first}, posd{mip[snd_half][j].second};
                            if (posa != posc && posa != posd && posb != posd && posb != posc) {
                                result.push_back(vector<int>());
                                result.back().push_back(num[posa]);
                                result.back().push_back(num[posb]);
                                result.back().push_back(num[posc]);
                                result.back().push_back(num[posd]);
                                sort(result.back().begin(), result.back().end());
                            }
                        }
                    }
                }
                
            }
            sort(result.begin(), result.end());
            result.erase(unique(result.begin(), result.end()), result.end());
            return result;
        }
    };

  • 0
    A

    sort(result.back().begin(), result.back().end());

    This is unnecessarily costly.

    It is easier and more efficient if you sort the num earlier in the beginning.


Log in to reply
 

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