Help on optimization, always becomes o(n^3)


  • 0
    P
    typedef unordered_map<int, vector<pair<int,int> > >::iterator It;
    typedef vector<pair<int,int> >::iterator SetIt;
    class Solution {
    public:
        vector<vector<int> > fourSum(vector<int> &a, int target) {
            int n = a.size();
           
            vector<vector<int> > result;
             if (n < 4) return result;
            std::sort(a.begin(), a.end());
            unordered_map<int, vector<pair<int,int> > > m;
            for (int i = 0; i < n; ++i) {
                for (int j = i+1; j < n; ++j) {
                    if (j == i) continue;
                    m[a[i]+a[j]].push_back(make_pair(i,j));
                }
            }
            
            for (int i = 0; i < n; ++i) {
                if (i > 0 && a[i] == a[i-1]) continue;
                for (int j = i+1; j < n; ++j) {
                    if (j > i+1 && a[j] == a[j-1]) continue;
                    int s = a[i]+a[j];
                    It it = m.find(target-s);
                    if (it == m.end()) continue;
                    vector<pair<int,int> > pairs = it->second;
                    int last_k = -1;
                    int last_m = -1;
                    for (SetIt setIt = pairs.begin(); setIt != pairs.end(); ++setIt) {
                        int k = setIt->first;
                        if (k <= j) continue;
                        int m = setIt->second;
                        // we have made sure that the i and j are not repeated, we have to make sure that k and m 
                        // are not repeated, we observe that
                        if (last_k != -1 && last_m != -1 && a[last_k] == a[k] && a[last_m]==a[m]) continue;
                        vector<int> cur_vec = {a[i],a[j],a[k],a[m]};
                        last_k = k;
                        last_m = m;
                        result.push_back(cur_vec);
                    }
                }
            }
            return result;
        }
    };

Log in to reply
 

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