对撞双指针---盛最多水的容器、三数之和、四数之和
一.11.盛最多水的容器
题目描述
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。
示例 2：
输入：height = [1,1] 输出：1
解题思路
根据木桶原理，决定面积大小的是短的一条边。利用对撞指针，移动两条边界，不断计算面积，记录当前面积，和已有max_area进行比较，如果更大，就记录到max_area。直到找到最大面积。
指针移动，移动短的那一边，就能让面积变大
代码实现
int maxArea(int* height, int heightSize) {
//找出两条线，使得与x轴共同构成的容器面积最大
//左指针向右移动，右指针向左移动，小的一条线移动，记录最大面积
//1.定义左右指针
int left = 0;
int right = heightSize - 1;
int maxArea = 0;
//2.对撞指针找最大面积maxArea
while(left < right)
{
//计算宽度
int width = right - left;
int area = 0;
if(height[left] > height[right])
{
area = height[right] * width;
right--;
}else
{
area = height[left] * width;
left++;
}
//记录最大面积
if(area > maxArea)
{
maxArea = area;
}
}
return maxArea;
}
总结
木桶原理，短的一边决定面积，对撞指针计算当前面积与已存面积进行比较，直到找出最大面积
二.15.三数之和
题目描述
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组
示例 1：
输入：nums = [-1,0,1,2,-1,-4] 输出：[[-1,-1,2],[-1,0,1]] 解释： nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。 nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。 nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。 注意，输出的顺序和三元组的顺序并不重要。
示例 2：
输入：nums = [0,1,1] 输出：[] 解释：唯一可能的三元组和不为 0 。
示例 3：
输入：nums = [0,0,0] 输出：[[0,0,0]] 解释：唯一可能的三元组和为 0 。
解题思路
令一个数a固定，求剩下两数之和，令其和等与-a，便可以找出三元组。
找两数之和等于-a，那便可以用对撞双指针。
要求找出所有三个数和为0，且不能重复的三元组。顺序不重要，重要的是要避免重复。怎么去重是这题的一个关键。
要实现去重，只需要把数组排序，让后一个值和前一个值比较，如果相同直接跳过就可以了。
其次，因为这题需要保存多个三元组数组，所以需要开辟内存空间
int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes)
int* nums : 输入数组 int numsSize : 数组长度 int* returnSize :输出找到的三元组个数
int** returnColumnSizes : 每个三元组有几个数字（这道题固定为3）
怎么排序？
使用qsort函数和cmp函数搭配使用就行，简单快捷。
//使用cmp函数和qsort函数
int cmp(const void* a, const void* b)
{
return (*(int*)a - *(int*)b);
}
qsort(void *base, size_t num, size_t size, int(*compar)(const void*));
qsort需要知道排序谁排在前面，cmp用来告诉qsort谁排在前面。
cmp函数： void*是万能指针，可以接受任意类型的指针。
const:：表示指针指向的内容不能被更改，保证安全规范。
(int*)： 将万能指针a强制转换成int*，这个指针指向的是int类型的数据。
*(int*)a - *(int*)b： 对转换后的指针解引用，拿到a指向的值，减去b指向的值，作为返回值。
负数表示a排在b的前面，正数表示b排在a前面。
qsort函数:：void *base是要排序的数组的首地址，比如要传int arr[10]，就传arr。
size_t num：数组元素个数。
size_t size：单个元素大小，就是字节数。
int(*compar)(const void*, const void*)：比较函数的指针，其实就是cmp。
代码实现
//使用cmp函数
int cmp(const void* a, const void* b)
{
return (*(int*)a - *(int*)b);
}
int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
//1.首先初始化returnSize, 给*returnColumnSizes开辟空间，定义结果数组**res并开辟空间
*retrunSize = 0;
int maxSize = numsSize * numsSize;//最多有n^2个三元组
int **res = (int**)malloc(sizeof(int*) * maxSize);
*returnColumnSizes = (int *)malloc(sizeof(int) * maxSize);
//2.实现排序
qsort(nums, numsSize, sizeof(int), cmp);
//3.先固定一个数nums[i]，对撞双指针计算三数之和，使之等于0
for(int i = 0; i < numsSize - 2; i++)
{
//对第一个数去重
if(i > 0 && nums[i] == nums[i - 1])
{
continue;
}
//双指针
int left = i + 1;
int right = numsSize - 1;
//双指针对撞
while(left < right)
{
int sum = nums[i] + nums[left] + nums[right];
//如果为0，则存入**res
if(sum == 0)
{
//给returnSize分配空间
res[*returnSize] = (int *)malloc(sizeof(int) * 3);//每个三元组固定3个元素
//存入3个数
res[*returnSize][0] = nums[i];
res[*returnSize][1] = nums[left];
res[*returnSize][2] = nums[right];
//标记三元组长度为3
(*returnColumnSizes)[*returnSize] = 3;
(*returnSize)++;
//左右指针开始去重
while(left < right && nums[left] == nums[left + 1])
{
left++;
}
while(left < right && nums[right] == nums[right - 1])
{
right--;
}
left++;
right--;
}
else if(sum < 0)
{
left++;
}
else{
right--;
}
}
}
return res;
}
总结
固定一个数，对撞双指针找三数和为0，优雅实现排序＋去重
三.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]]
解题思路
和上面的三数之和几乎一模一样！只不过是固定一个数变成了固定两个数，仅此而已。
不过我在初次写的时候犯了错，我想试着嵌套对撞指针来写，但是时间复杂度爆炸，所以走不通。
因此应该从左往右来进行整个过程。
代码实现
//1.定义排序函数，将数组从小到大排列
int cmp(const void* a, const void *b)
{
return (*(int *)a - *(int *)b);
}
int** fourSum(int* nums, int numsSize, int target, int* returnSize, int** returnColumnSizes) {
//对撞双指针可以求两数之和，那我们只需嵌套使用对撞双指针，即可找出四个数之和是target
//先排序，再去重，四个数都要去重
//2.初始化returnSize, 给结果res和returnColumnSizes赋予空间
*returnSize = 0;
//最多有n^3个四元组
int maxSize = numsSize * numsSize;
int **res = (int **)malloc(sizeof(int*) * maxSize);
*returnColumnSizes = (int *)malloc(sizeof(int) * maxSize);
//不足四个直接返回
if(numsSize < 4)
{
return res;
}
//3.调用排序函数
qsort(nums, numsSize, sizeof(int), cmp);
//4.对撞双指针
//定义固定双指针
for(int i = 0; i < numsSize - 3; i++)
{
//先给i和j去重
if(i > 0 && nums[i] == nums[i - 1])
{
continue;
}
for(int j = i + 1; j < numsSize - 2; j++)
{
if(j > i + 1 && nums[j] == nums[j - 1])
{
continue;
}
//定义对撞双指针
int left = j + 1;
int right = numsSize - 1;
//开启对撞
while(left < right)
{
long long sum = (long long)nums[i] + nums[j] + nums[left] + nums[right];
//第一种情况：和为target
if(sum == target)
{
//先给returnSize开空间
res[*returnSize] = (int*)malloc(sizeof(int) * 4);//四元组元素恒定为4
//再记录四元组
(*returnColumnSizes)[*returnSize] = 4;//四元组列恒定为4
res[*returnSize][0] = nums[i];
res[*returnSize][1] = nums[j];
res[*returnSize][2] = nums[left];
res[*returnSize][3] = nums[right];
(*returnSize)++;
//再给左右指针去重
while(left < right && nums[left] == nums[left + 1])
{
left++;
}
while(left < right && nums[right] == nums[right - 1])
{
right--;
}
left++;
right--;
}
//第二种情况：和不为target
//小于：left++
//大于：right--;
else if(sum < target)
{
left++;
}else
{
right--;
}
}
}
}
return res;
}
总结
固定两个数个数，对撞双指针找四数和为target，优雅实现排序＋去重
更多推荐
6
0- 0
已为社区贡献1条内容
所有评论(0)