29 lines
777 B
C++
29 lines
777 B
C++
#include "s0018_4sum.hpp"
|
|
|
|
vector<vector<int>> S0018::fourSum(vector<int>& nums, int target) {
|
|
int len = nums.size();
|
|
if (len < 4) {
|
|
return {};
|
|
}
|
|
vector<vector<int>> result{};
|
|
sort(nums.begin(), nums.end());
|
|
for (int i{1}; i < len - 2; i++) {
|
|
for (int j = len - 2; j > i; j--) {
|
|
for (int x{0}, y = len - 1; x < i && y > j;) {
|
|
if (nums[x] + nums[y] + nums[i] + nums[j] > target) {
|
|
y--;
|
|
} else if (nums[x] + nums[y] + nums[i] + nums[j] < target) {
|
|
x++;
|
|
} else {
|
|
vector<int> v = {nums[x], nums[i], nums[j], nums[y]};
|
|
if (std::find(result.begin(), result.end(), v) == result.end()) {
|
|
result.push_back(v);
|
|
}
|
|
x++;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
return result;
|
|
}
|