15. 三数之和
15. 三数之和https://leetcode.cn/problems/3sum/
题目描述：
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
解题思路：
我们先来看看题目：题目要求a+b+c=0，并且a、b、c三个数的下标各不相同，并且返回所有的可能性，并且要去重
我们首先可以确定一下大体思路：sort排序（有序）,有序可以被双指针或者二分来运用，这里我们使用排序+双指针
我们这里是三数之和，我们可以确定一个cur下标来遍历数组，一次一个数，然后问题就变成了剩下的数组的两数之和的问题！
我们两数之和就可以就可以运用双指针来降时间复杂度，left和right从两边到中间
这里比较考察大家的是left和right的边界问题，这里非常容易越界！！！
我们来结合本题的部分代码来理解
我们整个红色区域可以划分为[begin,right]（这里就不用left和right避免混乱，这里的begin代表红色的第一个，end是红色区域的最后一个的下一个），我们正常来说left<end，right>0的，但是我们这边下标访问涉及到left+1和right-1，所以left需要比end少一，也就是让left+1最大到end-1的位置，同理right>1
解题代码：
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> nnums;
int size = nums.size();
int cur = 0;
while (cur < size - 1)
{
int left = cur + 1;
int right = size - 1;
int a = (-1) * nums[cur];//找到两数之和为a的两个值
while (left < right)
{
if (nums[left] + nums[right] == a)
{
nnums.push_back({ nums[cur],nums[left],nums[right] });
while (right > 1 && nums[right] == nums[right - 1])
right--;
right--;
}
else if (nums[left] + nums[right] > a)
{
while (right > 1 && nums[right] == nums[right - 1])
right--;
right--;
}
else if (nums[left] + nums[right] < a)
{
while (left<size-1&&nums[left] == nums[left + 1])
left++;
left++;
}
}
while (cur<size-1&&nums[cur] == nums[cur + 1])
cur++;
cur++;
}
return nnums;
}
};18. 四数之和
18. 四数之和https://leetcode.cn/problems/4sum/
题目描述:
给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
0 <= a, b, c, d < n-
a、b、c和d互不相同 nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。
文章来源：https://www.toymoban.com/news/detail-707714.html
解题思路：
本题与上题一样，就是在三数之和的基础上外面再套一层文章来源地址https://www.toymoban.com/news/detail-707714.html
解题代码：
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
int size = nums.size();
vector<vector<int>>nnums;
for (int i = 0; i < nums.size();)
{
int cur = i+1;
while (cur < size - 1)
{
int left = cur + 1;
int right = size - 1;
long long a = (long long)target-nums[i] - nums[cur];//找到两数之和为a的两个值
while (left < right)
{
if (nums[left] + nums[right] == a)
{
nnums.push_back({ nums[i],nums[cur],nums[left],nums[right] });
while (right > 1 && nums[right] == nums[right - 1])
right--;
right--;
}
else if (nums[left] + nums[right] > a)
{
while (right > 1 && nums[right] == nums[right - 1])
right--;
right--;
}
else if (nums[left] + nums[right] < a)
{
while (left < size - 1 && nums[left] == nums[left + 1])
left++;
left++;
}
}
while (cur < size - 1 && nums[cur] == nums[cur + 1])
cur++;
cur++;
}
while (i < size - 1 && nums[i] == nums[i + 1])
i++;
i++;
}
return nnums;
}
};到了这里，关于【算法挨揍日记】day04——15. 三数之和、18. 四数之和的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
