【力扣-哈希表】8、四数之和（18）
题目描述
给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
0 <= a, b, c, d < na、b、c和d互不相同nums[a] + nums[b] + nums[c] + nums[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 = [2,2,2,2,2], target = 8
输出： [[2,2,2,2]]
复制代码思路
这里四数之和，并且限制了和为target 。 可以参考三数之和，使用双指针方法。在三数之和的方法基础上再加上一层for循环，算法步骤进行微调。
算法步骤：
- 先对数组nums进行排序
- 最外层for循环，只需要对第一个数字进行去重处理
- 第二层for循环，先进行去重处理
- 设置左右指针，遍历中间的数字，记录符合要求的四个数字
代码
// 参考三指针的方法
class Solution
{
public:
vector<vector<int>> fourSum(vector<int> &nums, int target)
{
// 先进性排序
sort(nums.begin(), nums.end());
vector<vector<int>> ret;
// 遍历
for (int i = 0; i < nums.size(); i++)
{
// 下面的这种剪枝是错误的 ， 因为可能要求的target是负值，而且小于每一个元素
// 上面的这种情况就会导致返回空数组
// if (nums[i] > target)
// {
// continue;
// }
// 第一个数已经出现过了，去重处理
if (i > 0 && nums[i] == nums[i - 1])
{
continue;
}
for (int j = i + 1; j < nums.size(); j++)
{
// j对应的数已经出现过了 ，所以也做去重处理
if (j > i + 1 && nums[j] == nums[j - 1])
{
continue;
}
// 设置左右指针
int left = j + 1;
int right = nums.size() - 1;
while (left < right)
{
// leetcode设置了限制用例 [1000000000,1000000000,1000000000,1000000000]
// 已经超出了整数的范围，所以这里使用相减的方式
// 或者使用long long int
if (nums[i] + nums[j] - target > -(nums[left] + nums[right]))
{
right--;
}
else if (nums[i] + nums[j] - target < -(nums[left] + nums[right]))
{
left++;
}
else
{
// 找到了四个数时，将其加入到结果数组中
ret.push_back({nums[i], nums[j], nums[left], nums[right]});
// 对右指针去重处理
while (right > left && nums[right] == nums[right - 1])
{
right--;
}
// 对做指针去重处理
while (right < left && nums[left] == nums[left + 1])
{
left++;
}
// 找到一组数字后，左指针右移，右指针左移
right--;
left++;
}
}
}
}
return ret;
}
};本文系转载，前往查看
如有侵权，请联系?cloudcommunity@tencent.com 删除。
本文系转载，前往查看
如有侵权，请联系?cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读
目录