Sponsored
Sponsored
This approach employs sorting the array and fixing two pointers while searching for the other two via a two-pointer method. This reduces the dimensionality of the problem stepwise.
Time Complexity: O(n^3), where n is the number of elements in the array due to three nested loops.
Space Complexity: O(1), excluding the space required for the output storage.
1#include <iostream>
2#include <vector>
3#include <algorithm>
4using namespace std;
5
6vector<vector<int>> fourSum(vector<int>& nums, int target) {
7 sort(nums.begin(), nums.end());
8 vector<vector<int>> result;
9 int n = nums.size();
10 for (int i = 0; i < n - 3; i++) {
11 if (i > 0 && nums[i] == nums[i - 1]) continue;
12 for (int j = i + 1; j < n - 2; j++) {
13 if (j > i + 1 && nums[j] == nums[j - 1]) continue;
14 int k = j + 1, l = n - 1;
15 while (k < l) {
16 int sum = nums[i] + nums[j] + nums[k] + nums[l];
17 if (sum == target) {
18 result.push_back({nums[i], nums[j], nums[k], nums[l]});
19 while (k < l && nums[k] == nums[k + 1]) k++;
20 while (k < l && nums[l] == nums[l - 1]) l--;
21 k++; l--;
22 } else if (sum < target) {
23 k++;
24 } else {
25 l--;
26 }
27 }
28 }
29 }
30 return result;
31}
32
33int main() {
34 vector<int> nums = {1, 0, -1, 0, -2, 2};
35 int target = 0;
36 vector<vector<int>> result = fourSum(nums, target);
37 for (auto &quad: result) {
38 cout << "[";
39 for (int i = 0; i < quad.size(); i++) {
40 cout << quad[i] << (i == quad.size() - 1 ? "" : ", ");
41 }
42 cout << "]\n";
43 }
44 return 0;
45}In C++, the algorithm exploits in-built sorting and vector data structure for dynamic array handling. The quadruplets matching the target are identified using sorted array and a fixed two-pointer scan, skipping over duplicate entries for the same sum.
This method reduces the four-sum problem by first reducing it to a three-sum problem, and then a two-sum problem using hash maps.
Time Complexity: O(n^2), considering the use of a hash map.
Space Complexity: O(n), for storing intermediate and potential pairs.
1
This solution uses a hash map to store potential pairs and provides an immediate reference to check against the target. Developing all valid pairs without duplicates requires keeping unique property checks on loop iterations.