// 4Sum class Solution { public: vector > fourSum(vector &a, int target) { int n = a.size(), old; multimap m; vector> r; sort(a.begin(), a.end()); for (int i = 0; i < n; ) { // a <= b < c <= d for (int j = i+1; j < n; ) { int t = target-a[i]-a[j]; auto it = m.equal_range(t); for (; it.first != it.second; ++it.first) { vector b{it.first->second, t-it.first->second, a[i], a[j]}; r.push_back(b); } old = a[j]; while (++j < n && a[j] == old); } // a < b = b <= c if (i+1 < n && a[i] == a[i+1]) { for (int j = i+2; j < n; ) { int t = target-a[i]*2-a[j]; auto it = lower_bound(a.begin(), a.begin()+i, t); if (it != a.begin()+i && *it == t) { vector b{*it, a[i], a[i], a[j]}; r.push_back(b); } old = a[j]; while (++j < n && a[j] == old); } } // a = a = a <= b if (i+2 < n && a[i] == a[i+2]) { int t = target-a[i]*3; auto it = lower_bound(a.begin()+i+3, a.end(), t); if (it != a.end() && *it == t) { vector b{a[i], a[i], a[i], t}; r.push_back(b); } } old = a[i]; while (i+1 < n && a[i+1] == old) i++; for (int j = 0; j < i; ) { m.insert(make_pair(a[j]+a[i], a[j])); old = a[j]; while (++j < n && a[j] == old); } i++; } return r; } };