4Sum Problem & Solution

See the 4sum problem on LeetCode.

C++ Solution

``````#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")

using namespace std;

static const int _=[](){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> result;

sort(nums.begin(), nums.end());

for (int i = 0; i < (int)nums.size() - 3; ++i) {
for (int j = i + 1; j < (int)nums.size() - 2; ++j) {
int k = j + 1;
int l = nums.size() - 1;
while (k < l) {
long sum = static_cast<long>(nums[i]) + nums[j] + nums[k] + nums[l];
if (sum < target) {
++k;
} else if (sum > target) {
--l;
} else {
result.push_back({nums[i], nums[j], nums[k], nums[l]});
while (k < nums.size() - 1 && nums[k] == nums[k + 1]) { ++k; }
while (l > 0 && nums[l] == nums[l - 1]) { --l; }
++k;
--l;
}
}

while (j < nums.size() - 1 && nums[j] == nums[j + 1]) { ++j; }
}

while (i < nums.size() - 1 && nums[i] == nums[i + 1]) { ++i; }
}

return result;
}
};
``````

Start Here

Many paths, there are. Follow yours, you must.