Always TLE,can anybody help me?


  • 0
    F

    I studied other person's method and write it in c++; but Always TLE,can anybody help me?

    class Solution {
    public:
    struct node {
    node(int a, int ai, int b, int bi):a(a),ai(ai),b(b),bi(bi){}
    int a;
    int ai;
    int b;
    int bi;
    };

    vector<vector<int> > fourSum(vector<int> &num, int target) {
        
        vector<vector<int> > res;
        
        if (num.size() < 4) {
            return res;
        }
        
        sort(num.begin(), num.end());
        
        map<int, vector<node>> mp;
        for (int i = 0; i < num.size(); i++) {
            for (int j = i+1; j < num.size(); j++) {
                int sum = num[i] + num[j];
                if (mp.find(sum) == mp.end()) {
                    mp.insert(make_pair(sum, vector<node>()));
                }
                node tmp(num[i], i, num[j], j);
                mp[sum].push_back(tmp);
            }
        }
        
        map<int, vector<node>>::iterator iter = mp.begin();
        map<int, vector<node>>::reverse_iterator  iter2 = mp.rbegin();
        while (iter!= mp.end() && iter2 != mp.rend() && iter->first <= iter2->first) {
            if (iter->first + iter2->first > target) {
                ++iter2;
                continue;
            }
            if (iter->first + iter2->first < target) {
                ++iter;
                continue;
            }
            if (iter->first == iter2->first) {
                for (int i = 0; i < iter->second.size(); i++) {
                    if ((iter->second)[i].a != (iter->second)[i].b) {
                        continue;
                    } else {
                        int j ;
                        for (j = i+1; j < iter->second.size(); j++) {
                            if ((iter->second)[j].a != (iter->second)[j].b) {
                                break;
                            }
                            if ((iter->second)[j].ai <= (iter->second)[i].bi) {
                                continue;
                            } else {
                                vector<int> tmp;
                                tmp.push_back((iter->second)[i].a);
                                tmp.push_back((iter->second)[i].b);
                                tmp.push_back((iter->second)[j].a);
                                tmp.push_back((iter->second)[j].b);
                                res.push_back(tmp);
                                break;
                            }
                        }
                        break;
                    }
                }
                ++iter;
                ++iter2;
            } else {
                for (int i = 0; i < iter->second.size(); i++) {
                    if (i > 0 && iter->second[i].a == iter->second[i-1].a && iter->second[i].b == iter->second[i-1].b) {
                        continue;
                    }
                    for (int j = 0; j < iter2->second.size(); j++) {
                        if ((iter2->second)[j].ai <= (iter->second)[i].bi) {
                            continue;
                        }
                        if (j > 0 && iter->second[j].a == iter->second[j-1].a && iter->second[j].b == iter->second[j-1].b) {
                            continue;
                        }
                        vector<int> tmp;
                        tmp.push_back((iter->second)[i].a);
                        tmp.push_back((iter->second)[i].b);
                        tmp.push_back((iter2->second)[j].a);
                        tmp.push_back((iter2->second)[j].b);
                        res.push_back(tmp);
                    }
                }
                ++iter;
                ++iter2;
            }
        }
    
        return res;
    }
    

    };


Log in to reply
 

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