算法——双指针（day4)
15.三数之和
题目解析：
这道题目说是三数之和，其实这和我们之前做过的两数之和是一个规律的~无非就是我们需要实时改动target的值。先排好序，然后固定一个数取其负值作target，然后我们再从除固定数以外的范围内寻找两数之和为target的数，这样再与固定数相加就得到0了，形成三元数组。
算法解析：
这就是两数和的核心图解，唯一区别就是我们的target值是随着固定数的变化而发生改变的~
废话不多说，本题的难点就在于去重以及去重时的越界问题。因为按照题目规定类似于
【-1，0，-1】与【-1，-1，0】这种会算重复项只能取其一，而这也是我们优先选择排序的原因，在排行序后二者就变为【-1，-1，0】，更容易去重。
去重分两个阶段，一是【left,right】范围之间的去重，另一个是固定数first遍历数组的去重。
所以我们给出的去重方案就是观察移动前后的数值是否相同，如果相同那就再移动一位，直到不同为止。不过这样也引发了新的问题：越界~
我们发现left与right的选取是需要在【left,rigtht】这个界限里面的，所以只需要加上一层条件即可（left<right)~
固定数first同理：
代码：
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> ret;
sort(nums.begin(), nums.end());
int n = nums.size();
int first = 0;
while (first <= n - 3)
{
//小优化
if (nums[first] > 0) break;
int left = first + 1;
int right = n - 1;
int target = -nums[first];
//一轮比较
while (left < right)
{
int sum = nums[left] + nums[right];
if (sum > target)
{
--right;
}
else if (sum < target)
{
++left;
}
else
{
ret.push_back({ nums[first],nums[left],nums[right] });
right--;
left++;
//left与right去重
while (left < right && nums[right + 1] == nums[right])
{
right--;
}
while (left < right && nums[left - 1] == nums[left])
{
left++;
}
}
}
//固定数去重
first++;
while (first < n && nums[first - 1] == nums[first])
{
first++;
}
}
return ret;
}
};18.四数之和
题目解析：
四数之和别看多了一个数，其实和三数之和还是同一个模板，没有本质区别
算法解析：
找四数之和我们可以先拆分成固定数a与三数之和，那么三数之和的值就得为target-a。这样a与三数之和才相加才可以变为target，而在三数之和中就得拆分成固定数b与两数之和，那么两数之和的值就得为target-a-b，这样才能与b相加得到target-a。
所以只要在三数之和的代码中把控好target-a-b的值就行了，除此之外再多加一个对固定数a的去重就好了~
代码：
在三数之和外套一层固定数a的循环以及去重复，另外改变目标值t变为target-a-b就差不多了。
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();
int a = 0;
//固定数a
while (a <= n - 4)
{
//固定数b
int b = a + 1;
while (b <= n - 3)
{
int left = b + 1;
int right = n - 1;
//防止数据溢出强转类型
long long t = (long long)target - nums[b] - nums[a];
while (left < right)
{
int sum = nums[left] + nums[right];
if (sum > t)
{
--right;
}
else if (sum < t)
{
++left;
}
else
{
ret.push_back({ nums[a],nums[b],nums[left],nums[right] });
right--;
left++;
//一级去重复
while (left < right && nums[right + 1] == nums[right])
{
right--;
}
while (left < right && nums[left - 1] == nums[left])
{
left++;
}
}
}
//二级去重
b++;
while (b < n && nums[b - 1] == nums[b])
{
b++;
}
}
//三级去重
a++;
while (a < n && nums[a - 1] == nums[a])
{
a++;
}
}
return ret;
}
};
原文地址：https://blog.csdn.net/fax_player/article/details/140555208
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！