题目
给你一个由 n
个整数组成的数组 nums
,和一个目标值 target
。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]]
(若两个四元组元素一一对应,则认为两个四元组重复):
0 <= a, b, c, d < n
a
、b
、c
和d
互不相同nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案
题目解析
1.选择的四个数字位置不能是一样的
2.题目中的a,b,c,d各不相同
3.可以按照任意顺序返回答案
讲解算法原理
解法一
排序+暴力枚举+利用set去重即可(该方法超时,不做讲解)
解法二
排序+双指针
先确定一个数值a,再用target代表四个数值的和减去a
1.依次固定一个数a
2.在a后面的区间内,利用“三数之和”找到三个数,使得三个数的和等于target-a即可;
----------------------------------->
1.依次固定一个数b;
2.在b后面的区间里,利用双指针找到两个数,使得这两个函数的和等于target-a-b;
细节处理(三个数之和已经讲过)
1.不重
2.不漏
代码
class Solution
{
public:
vector<vector<int>> fourSum(vector<int>& nums, int target)
{
vector<vector<int>> ret;
//排序
sort(nums.begin(), nums.end());
//利用双指针解决问题
int n = nums.size();
for(int i = 0; i < n; i++)
{
//利用三数之和
for(int j = i + 1; j < n; j++) //固定数b
{
//双指针解法
int left = j + 1, right = n - 1;
int aim = target - nums[i] - nums[j];
while(left < right)
{
int sum = nums[left] + nums[right];
if(sum < aim)
left++;
else if(sum > aim)
right--;
else
{
ret.push_back({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--;
}
}
//去重
j++;
while(j < n && nums[j] == nums[j - 1])
j++;
}
//去重三
while(i < n && nums[i] == nums[i - 1])
i++;
}
return ret;
}
};
标签:四数,target,nums,++,int,算法,right,讲解,left
From: https://blog.csdn.net/2301_78350690/article/details/137177330