My C++ solution using hashtable
My idea is to sort num first, then build a hashtable with the key as the sum of the pair and the value as a  vector storing all pairs of index of num that havin
My idea is to sort num first, then build a hashtable with the key as the sum of the pair and the value as a  vector storing all pairs of index of num that having the same sum. In this way, all elements stored in hashtable has a order that duplicate pairs are neighbors. Therefore scanning the vector in the hashtable we only put non duplicate elements into the final answer vvi.\n\nIs this method O(n^2) ? or Does anyone can improve it to O(n^2);\n\n\n\n        class Solution{ //using hashtable, avg O(n^2)\n    \n    public:\n    \n        vector<vector<int> > fourSum(vector<int> &num, int target){\n            vector<vector<int> > vvi;\n            int n = num.size();\n            if(n < 4) return  vvi;\n            \n            sort(num.begin(), num.end());        \n            unordered_map<int, vector<pair<int, int>> > mp;\n            for(int i = 0; i < n; i++){\n                for(int j = i + 1; j < n; j++){\n                    mp[num[i]+num[j]].push_back(make_pair(i,j));\n                }\n            }\n            \n            for(int i = 0; i < n; i++){\n                if(i>0 && num[i] == num[i-1]) continue;\n                for(int j = i + 1; j < n; j++){\n                    if(j > i + 1 && num[j] == num[j-1]) continue;\n                    int res = target - num[i] - num[j];\n                    if(mp.count(res)){\n                        for(auto it = mp[res].begin(); it != mp[res].end(); it++){\n                            int k = (*it).first, l = (*it).second;\n                            if(k > j){ // k>j make sure that the second pair has bigger values than the first pair.\n                                if(!vvi.empty() && num[i]==vvi.back()[0] && num[j]==vvi.back()[1]\n                                && num[k]==vvi.back()[2] && num[l] == vvi.back()[3]){\n                                    continue; //if the obtained 4 elements are the same as previous one continue to next\n                                }\n                                vector<int> vi={num[i], num[j], num[k], num[l]};\n                                vvi.push_back(vi);\n                            } // if k>j\n                            \n                        }//for it\n                    }//if\n                }// forj\n            }//for i\n            return vvi;\n        }\n      };
[]