NC348. 四数之和
描述
示例1
输入:
[2,0,-2,3,-3,0],0
输出:
[[2,-2,0,0],[3,-3,0,0],[2,-2,3,-3]]
C++ 解法, 执行用时: 7ms, 内存消耗: 408KB, 提交时间: 2022-07-25
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int整型vector
* @param target int整型
* @return int整型vector<vector<>>
*/
vector<vector<int> > fournumber(vector<int>& nums, int target) {
vector<vector<int>>vec;
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size(); i++)
{
if (nums[i] > target && nums[i] >= 0 && target >= 0)
break;
if (i > 0 && nums[i] == nums[i - 1])
continue;
for (int j = i + 1; j < nums.size(); j++)
{
if (nums[i] + nums[j] > target && (nums[i] + nums[j]) >= 0 && target >= 0)
break;
if (j > i + 1 && nums[j] == nums[j - 1])
continue;
int left = j + 1;
int right = nums.size() - 1;
while (left < right)
{
if (nums[i] + nums[j] + nums[left] + nums[right] < target)
left++;
else if (nums[i] + nums[j] + nums[left] + nums[right] > target)
right--;
else
{
vec.push_back(vector<int> {nums[i], nums[j], nums[left], nums[right]});
while (left < right && nums[left] == nums[left + 1])
left++;
while (left < right && nums[right] == nums[right - 1])
right--;
left++;
right--;
}
}
}
}
return vec;
}
};
C++ 解法, 执行用时: 7ms, 内存消耗: 412KB, 提交时间: 2022-06-28
class Solution {
public:
vector<vector<int> > fournumber(vector<int>& nums, int target) {
vector<vector<int>> z;
if (nums.size() < 4) {
return z;
}
sort(nums.begin(), nums.end());
int h = nums.size();
for (int a = 0; a < h - 3; a++) {
if (a > 0 && nums[a] == nums[a - 1]) {
continue;
}
if ((long) nums[a] + nums[a + 1] + nums[a + 2] + nums[a + 3] >
target) {
break;
}
if ((long) nums[a] + nums[h - 3] + nums[h - 2] + nums[h - 1]
< target) {
continue;
}
for (int b = a + 1; b < h - 2; b++) {
if (b > a + 1 && nums[b] == nums[b - 1]) {
continue;
}
if ((long) nums[a] + nums[b] + nums[b + 1] + nums[b + 2] >
target) {
break;
}
if ((long) nums[a] + nums[b] + nums[h - 2] + nums[h - 1] <
target) {
continue;
}
int c = b + 1;
int d = h - 1;
while (c < d) {
int sum = nums[a] + nums[b] + nums[c] + nums[d];
if (sum == target) {
z.push_back({nums[a], nums[b], nums[c], nums[d]});
while (c < d && nums[c] == nums[c + 1]) {
c++;
}
c++;
while (c < d && nums[d] == nums[d - 1]) {
d--;
}
d--;
} else if (sum > target) {
d--;
} else {
c++;
}
}
}
}
return z;
}
};
C++ 解法, 执行用时: 7ms, 内存消耗: 472KB, 提交时间: 2022-07-08
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int整型vector
* @param target int整型
* @return int整型vector<vector<>>
*/
vector<vector<int> > fournumber(vector<int>& nums, int target) {
// write code here
int i, j, k, l;
sort(nums.begin(), nums.end());
vector<vector<int> > ans;
int n = nums.size();
for(int i = 0; i < n-3; i++)
{
if(i && nums[i] == nums[i-1])
continue;
for(int j = i+1; j < n-2; j++)
{
if(j > i+1 && nums[j] == nums[j-1])
continue;
int t = target - nums[i] - nums[j];
k = j+1;
l = n-1;
while(k < l)
{
int val = nums[k] + nums[l];
if(val > t)
{
l--;
}
else if(val < t)
{
k++;
}
else
{
ans.push_back({nums[i], nums[j], nums[k], nums[l]});
k++;
l--;
while(k < l && nums[k] == nums[k-1]) k++;
while(k < l && nums[l] == nums[l+1]) l--;
}
}
}
}
return ans;
}
};
C++ 解法, 执行用时: 8ms, 内存消耗: 404KB, 提交时间: 2022-04-16
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int整型vector
* @param target int整型
* @return int整型vector<vector<>>
*/
vector<vector<int> > fournumber(vector<int>& nums, int target) {
// write code here
vector<vector<int>> res;
if(nums.size() < 4){
return res;
}
sort(nums.begin(),nums.end());
int length = nums.size();
for(int first = 0;first<length - 3;first++){
if(first > 0 && nums[first] == nums[first-1]){
continue;
}
if ((long) nums[first] + nums[first + 1] + nums[first + 2] + nums[first + 3] > target) {
break;
}
if ((long) nums[first] + nums[length - 3] + nums[length - 2] + nums[length - 1] < target) {
continue;
}
for(int second = first+1;second<length - 2;second++){
if(second > first+1 && nums[second] == nums[second-1]){
continue;
}
if ((long) nums[first] + nums[second] + nums[second + 1] + nums[second + 2] > target) {
break;
}
if ((long) nums[first] + nums[second] + nums[length - 2] + nums[length - 1] < target) {
continue;
}
int left = second+1;
int right = length - 1;
while(left<right){
int sum = nums[first]+nums[second]+nums[left]+nums[right];
if(sum == target){
res.push_back({nums[first],nums[second],nums[left],nums[right]});
while (left < right && nums[left] == nums[left + 1]) {
left++;
}
left++;
while (left < right && nums[right] == nums[right - 1]) {
right--;
}
right--;
}else if(sum > target){
right--;
}else{
left++;
}
}
}
}
return res;
}
};
C++ 解法, 执行用时: 8ms, 内存消耗: 412KB, 提交时间: 2022-03-27
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int整型vector
* @param target int整型
* @return int整型vector<vector<>>
*/
vector<vector<int> > fournumber(vector<int>& nums, int target) {
vector<vector<int>> result;
sort(nums.begin(),nums.end());
for(int i = 0 ; i< int(nums.size())-3;++i){
if(i>0&&nums[i]==nums[i-1])
continue;
for(int j = i+1; j < int(nums.size())-2 ; ++j){
if(j>i+1 && nums[j]==nums[j-1])
continue;
int left = j +1;
int right = nums.size()-1;
while(left < right){
if(nums[i]+nums[j]+nums[left]+nums[right]-target>0){
--right;
while(left<right&& nums[right]==nums[right+1]) --right;
}
else if (nums[i]+nums[j]+nums[left]+nums[right]-target<0){
left++;
while(left<right&& nums[left]==nums[left-1]) ++left;
}
else{
result.push_back({nums[i],nums[j],nums[left],nums[right]});
left++;
right--;
while(left<right+1&& nums[left]==nums[left-1]) ++left;
while(left<right+1&& nums[right]==nums[right+1]) --right;
}
}
}
}
return result;
}
};