四数之和（排序+双指针）1
需积分: 0 43 浏览量
2022-08-03
13:53:54
上传
评论
收藏 531KB PDF 举报
四数之和
给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元
素 a
，
b
，
c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四
元组。
注意：答案中不可以包含重复的四元组。
示例 1：
输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
示例 2：
输入：nums = [], target = 0
输出：[]
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
//参照三数之和求解
sort(nums.begin(),nums.end());
vector<vector<int> > res;
if(nums.size()<4)
return res;
int a,b,left,right;
for(a=0;a<=nums.size()-4;a++)
{
if(a>0&&nums[a]==nums[a-1]) continue;//连续相同的跳过
for(b=a+1;b<=nums.size()-3;b++)
{
if(b>a+1&&nums[b]==nums[b-1]) continue;
//双指针查找剩余两个
left=b+1;
right=nums.size()-1;
while(left<right)
{
if(nums[a]+nums[b]+nums[left]+nums[right]<target)
left++;
else if(nums[a]+nums[b]+nums[left]+nums[right]>target)
right--;
else
评论0