双指针算法题目

阑梦清川

发布于 2025-02-24 22:22:11

650

文章被收录于专栏：学习成长指南学习成长指南

1.盛水最多的容器

我认为这个题目的这个核心灵魂就是下面的这个图片了，理解了下面的这个思想，我们就可以明白这个双指针在这个题目里面是如何进行使用的：

下面的这个就是一组假设的数据，通过下面的这个案例，我们就可以理解为什么这个指针指向的小的数据需要进行移动：

1）	假设初始时刻这个left和right分别指向我们的6.4两个数据，这个时候我们进行盛水：取决于最短的板子，因此这个时候最高的盛水位置就是两个指针指向的数据里面的较小的哪一个，这个时候我们的这个4和里面的两个数字组合，这个时候我们的这个宽度是减小的，因此这个时候成水量肯定是下降的；
2）	但是如果遇到一个比我们的这个4更大的数据，这个时候高度不变，宽度还是减小的，因此无论如何，我们的这个4和里面的数据比较就没有意义了，这个时候我们的这个思路就是让right–即可；综合上面的这个思路，我们就是让这个left和right分别指向我们的这个数组的左边和右边，然后两个进行比较，小的那个就会向中间进行移动（left小就是右移，righht就是左移）；
3）	v表示的就是这个宽度乘以这个高度（取决于两个数组元素的较小值，使用min函数获得）；
4）	ret表示每一次比较之后的数据更新（比如第一次盛水10，第三次的时候发现了一个20的，这个时候我们的这个ret就会变成20）；
5）	最后我们的这个ret里面的这个数据就是我们的最大的盛水量，因此这个ret就是我们的返回值；

2.有效的三角形的个数

题目：

1）	首先对于这个给出来的这个数组里面的数据，我们需要对于这个数组元素进行排序，让这个数组变成是一个有序的数组；
2）	我们把这个最大的数据定义为这个目标值，只要左边的数据里面的两个数据的和大于这个最大值就可以了（如果不是有序的，我们需要判断任意的两个数字的和大于第三个，否则有序只需要判断一组，这个就是我们进行排序的原因）；
3）	当我们的left+right>最大的数据的时候，我们的这个right–(这个时候的left,right之间的数据都是符合条件的)，这个直接加上right-left组即可；
4）	a+b<=c的时候，肯定是不符合题目要求的，因此这个时候我们选择left++;

代码说明：

1)	for外层的这个循环就代表的是我们的这个一组c的统计组数；
2）	里面的这个for表示的就是我们的这个c确定的时候，需要进行几次判断；
3）	int i=n-1表示的就是我们的这个数组里面的这个最大数对应的下标；
4）	i>=2是因为我们是三个数据，至少下标是2，而不是从0开始的；

3.原剑指offer（和为s的两个数字)

下面的这个就是这个题目的思路，left+right和我们的这个目标值进行比较，小于的话就让这个left++,大于的话就让这个right–，相等就返回这两个数据即可；

下面的这个就是一层循环：因为我们的这个else里面的这个是返回两个值：这个返回值的方式需要看一下；

其次就是我们的编译器觉得如果走不到这个else里面是不是这个题目就没有返回值呢，因此这个时候我们为了照顾这个编译器，选择在这个循环的外面加上这个return new int[]{0}这个其实是没有实际含义的；

4.三个数字的和

这个题目主要困难的地方就是需要去重：

1）	我们的这个返回值是一个嵌套的这个list，因此开始需要创建一个ret到时候作为返回值；
2）	我们这个题目由上面的题目的思想，就是第一个数字是-4的时候，我们只需要在后面的这个数据里面看看是不是有相加为4的数字就可以了，因此我们的这个4就是target，这样的话，这个题目和上面的这个题目就是相同的；
3）	但是当我们的这个nums[i]>0的时候，后面的这个数据也是大于0的，这个时候不可能相加为0，因此这个13行我们进行了这个优化，直接退出；
4）	下面的这个11行开始的部分就是看看两数字的和是不是等于我们的这个target数值，和上面的题目不一样的地方就是，我们需要进行去重；
5）	我们找到之后，就是18行的，我把这个数据放到这个ret里面去，就是一个返回值了，这个时候我们还需要继续进行判断的；
6）	21行是进行的这个去重，就是我们连续两个数据都是一样的时候，直接跳过去，22行也是去重，只不过一个是左边的，一个是右边的；
7）	这个时候，全部完成，我们的这个target需要更换了，就让i++，看看这个target和之前的是不是一样的，如果是一样的，这个时候我们还是要进行去重的，
8）	因为我们的这个26行里面的去重之后，i++就是我们想要的，因此这个6行里面的这个i++就可以去掉了，这个地方需要我们灵活处理；