不知道三数之和思路可以在开始本题前先看:(7)双指针练习:三数之和-CSDN博客
四数之和
给你一个由n
个整数组成的数组nums
,和一个目标值target
。请你找出并返回满足下述全部条件且 不重复的四元组[nums[a], nums[b], nums[c], nums[d]]
(若两个四元组元素一一对应,则认为两个四元组重复):
1.0 <= a, b, c, d < n
2.a
、b
、c
和d
互不相同
3.nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。
思路解析:
本题与三数之和的思路基本一致,即排序+双指针算法,根据表达式nums[a]+nums[b]+nums[c]+nums[d] = target
,所以可以得出算式nums[c]+nums[d] = target-nums[a]-nums[b]
,所以先确定两个基数nums[a]
和nums[b]
,再通过双指针算法得到nums[c]和nums[d]
📌
注意本题有数据溢出的情况
参考代码:
/*
* @lc app=leetcode.cn id=15 lang=cpp
*
* [15] 三数之和
*/
// @lc code=start
class Solution
{
public:
vector<vector<int>> fourSum(vector<int> &nums, int target)
{
vector<vector<int>> ret;
sort(nums.begin(), nums.end());
int sz = nums.size();
for (int i = 0; i < sz;)
{
// 三数之和思路
for (int j = i + 1; j < sz;)
{
// 注意整型范围
long long rest = (long long)target - nums[i] - nums[j];
int left = j + 1;
int right = sz - 1;
// 两数之和思路
while (left < right)
{
int sum = nums[left] + nums[right];
if (sum > rest)
{
right--;
}
else if (sum < rest)
{
left++;
}
else
{
ret.push_back({nums[i], nums[j], nums[left], nums[right]});
left++;
right--;
while (left < right && nums[left] == nums[left - 1])
{
left++;
}
while (left < right && nums[right] == nums[right + 1])
{
right--;
}
}
}
j++;
while (j < sz && nums[j] == nums[j - 1])
{
j++;
}
}
i++;
while (i < sz && nums[i] == nums[i - 1])
{
i++;
}
}
return ret;
}
};
// @lc code=end