个人主页:Lei宝啊
愿所有美好如期而遇
该题目链接:
前言:
做这道题之前建议先看一下这道题目:三数之和,思路很相似。
算法原理:
双指针法,不一定是说就要使用指针,只是一种形象的说法,在数组中,我们一般将数组下标当做指针。
这道题我们仍然延续之前的思路,固定一个数,去遍历剩下的三个数和是否等于target-固定数,这样剩下的就是三数之和,再固定一个数,去看剩下的两个数和是否等于target-固定数1-固定数2,如果相等,那么就将这两个数以及固定数尾插进vector<vector<int>>,然后去重,我们要去三次重,两个数相等尾插后去重,固定数2去重,固定数1去重。
图示:
后面的情况不再往下画。
代码:
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target)
{
sort(nums.begin(), nums.end());
vector<vector<int>> vv;
for (int i = 0; i < nums.size(); )
{
long long target1 = target - nums[i];
for (int j = i + 1; j < nums.size(); )
{
int left = j + 1;
int right = nums.size() - 1;
long long target2 = target1 - nums[j];
while (left < right)
{
if (nums[left] + nums[right] < target2)
{
left++;
}
else if (nums[left] + nums[right] > target2)
{
right--;
}
else
{
vv.push_back({ nums[left],nums[right],nums[i],nums[j] });
left++;
right--;
while (left < right && nums[left] == nums[left - 1])
{
left++;
}
while (left < right && nums[right] == nums[right + 1])
{
right--;
}
}
}
j++;
while (j < nums.size() && nums[j] == nums[j - 1])
{
j++;
}
}
i++;
while (i < nums.size() && nums[i] == nums[i - 1])
{
i++;
}
}
return vv;
}
};