当前位置：首页 > news >正文

双指针算法（二）

news 来源：原创 2025/8/20 13:59:11

一、力扣611——有效三角形的个数

二、牛客网3734——和为S的两个数字

三、力扣15——三数之和

四、力扣18——四数之和

一、力扣611——有效三角形的个数

题目如下：

这里我们先认识如何判断是个三角形，a+b>c,a+c>b,b+c>a即为三角形

这里我们假设a<=b<=c，这里我们c是最大的，c加任何一个正数都比a或b大，所以我们只需要判断a+b是否>c就可以了。

所以我们这里算法思想是

先对这个数组进行排序，然后固定最大数，定义left和right，left从0开始，right从第二大的数开始，判断left+right是否大于这个最大的数。
如果left+right > 这个最大的数，那么说明left之后的数加上right所指向的数都大于这个固定的数。这个总共有right-left个个数符合这个条件。right再--，判断前一个加上left是否大于，直到left个right遍历完除去固定数的数组。

如果left+right<这个最大的数，这个时候left++，再继续判断。

固定7后，再固定第二大的数，继续上面的算法逻辑就行。

代码如下：

class Solution {
public:int triangleNumber(vector<int>& nums) {int size = nums.size();sort(nums.begin(),nums.end());int n = size - 1;   //最开始固定数组下标的最大值int count = 0;while(n >= 2){int left = 0;int right = n -1;while(right > left){if(nums[left] + nums[right] <= nums[n]){left++;continue;}else{int cnt = right - left;count += cnt;right--;}}n--;}return count;}
};

二、牛客网3734——和为S的两个数字

题目如下：

这里是一个有序数组，对于一个有序数组的操作，我们优先要有双指针和二分的思想，双指针效果更优，后面也会给大家讲解二分算法。

这里从数组找到两个数之和等于S，这里我们还是定义两个指针left和right分别指向数组的头和尾，这两个指针所指向的位置相加。

如果array[left]+array[right] > S,我们让right--，因为这是一个升序的有序数组。right-1所指向的值是比right所指向的值要小的。
如果array[left]+array[right] < S,我么让left++，left+1所指向的值是比left指向的值要大的。
根据left和right不断遍历这个数组，如果找到了array[left]+array[right] == S，返回left和right所指向的值，没找到返回一个空数组。

代码如下：

class Solution {
public:vector<int> FindNumbersWithSum(vector<int> array,int sum) {vector<int> v1;int left = 0;int right = array.size() - 1;while(left < right){if(array[left] + array[right] < sum){left++;}else if(array[left] + array[right] > sum){right--;}else {v1.push_back(array[left]);v1.push_back(array[right]);return v1;}}return v1;}};

三、力扣15——三数之和

题目如下：

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

这里还要注意不可以包含重复的三元组。

其实这道题的解题思路是和有效三角形的个数是一样的。只是这道题要求不能重复。

所以我们就多了一个去重的操作。

这里满足的条件是 nums[i] + nums[j] + nums[k] == 0 ，说明要么这三个数全是0，要么就存在一个负数。我们先对这个数组进行排序，我们固定第一个数（0或负数），定义left为固定数+1，right为这个数组的尾部。

我们要满足三个数之和为0的话，这里我们固定了-4，所以我们只需要找到另外两个数相加等于4就行。跟上面找两数之和的思路一模一样，这里也不直接细讲了。

只是这里我们不是找到了就直接返回，而是要继续找，所以当找到这个符合条件left和right所指向位置的时候，left++，right--，缩小范围继续寻找。

固定完-4之后，固定-2依次往下，直到这个固定的数>0就结束了，这是一个小优化，因为如果这个数大于0的话，那么left和right都在这个数的右边，他们相加无论如何都不可能等于0，只会大于0.

算法思路就是如上，接下来我们讲如何去重

我们可能第一想法是用一个unordered_set容器，把符合条件的三元组全放到这个容器中，就能完成去重，那我有其他办法在遍历数组的方式上完成去重呢？

答案是有的

当我们是这种情况的时候，left，right所指向的数之和==4，left后一个也是0，这样不就重复了吗，所以遇到这样的情况，我们直接left++，直到left所指向的位置不等于0。

所以我们可能会这样写代码

while(nums[left] == nums[left+1]) left++

但我不推荐这样写，如果我们完成去重操作，对这个固定的数，left，right都这样写的话，有个测试用例会出错。

这里给大家画图讲解一下为什么会出错。

这里我们完成固定-4的操作后，我们接下来固定-1，按照我们刚刚写的逻辑的话，我们会直接跳过这个-1，固定下一个-1，这就漏了一个用例了，当我们固定第一个-1的时候，[-1,-1,1]是满足条件的，如果直接跳过了，这一组的测试用例就会不通过。

所以我们去重操作可以这样写。

 while(nums[left] == nums[left - 1])

这里我们防止left和right出界，我们可以在去重操作增加一个判断——left < right

代码如下：

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {sort(nums.begin(),nums.end());vector<vector<int>> vec;int size = nums.size();int n = 0;while(n < size){if(nums[n] > 0) break;int left = n + 1;int right = size - 1;while(left < right){int target = -nums[n];if(nums[left] + nums[right] < target) left++;else if(nums[left] + nums[right] > target) right--;else{vec.push_back({nums[n],nums[left],nums[right]});left++;right--;while(left < right &&nums[left] == nums[left - 1]) left++;while(left < right &&nums[right] == nums[right + 1]) right--;}}n++;while(n < size  && nums[n] == nums[n - 1]) n++;}return vec;}
};

四、力扣18——四数之和

题目如下：

四数之和等于给出的一个target，就是让我们在这个数组上找四个数相加=target。

在我们讲解了两数之和，三数之和，这里大家应该都会有一个思路吧

这里我们固定第一个数-2，这个问题就转化成在这个数组中找到三数之和找到target = 3的数，然后我们在除去固定数的数组中，再固定第一个数-1，这个问题就转化成在这个数组中找到两数之和找到target = 4，当然在我们所画的数组并不存在。因为这只是我们固定-2的结果，我们要一直往后固定，一直模拟这个算法。

这道题也是需要去重的，去重的思路和三数之和的思路一样，我也不继续细说啦

代码如下：

class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {sort(nums.begin(),nums.end());vector<vector<int>> vec;int size = nums.size();int n = 0;while(n < size){int Bindn = n + 1;while(Bindn < size){int left = Bindn + 1;int right = size - 1;while(left < right){long cnt = (long)target - nums[n] - nums[Bindn];if(nums[left] + nums[right] < cnt) left++;else if(nums[left] + nums[right] > cnt) right--;else{vec.push_back({nums[n],nums[left],nums[right],nums[Bindn]});left++;right--;while(left < right &&nums[left] == nums[left - 1]) left++;while(left < right &&nums[right] == nums[right + 1]) right--;}}Bindn++;while(Bindn < size  && nums[Bindn] == nums[Bindn - 1]) Bindn++;}n++;while(n < size && nums[n] == nums[n - 1]) n++;}return vec;}
};

一、力扣611——有效三角形的个数

二、牛客网3734——和为S的两个数字

三、力扣15——三数之和

四、力扣18——四数之和

相关文章：