前言
本专栏的上篇，讲述了双指针的一些基础的算法习题
今天我们来学习更进一步的双指针用法吧
其实也是大相径庭，和前面的差不多，只不过题目难了一些
fellow me
有效的三角形个数
思路
第一种解法就是——暴力求解（会超时）
三层 for 循环枚举出所有的三元组，并且判断是否能构成三角形。
虽然说是暴力求解，但是还是想优化一下：
判断三角形的优化：
如果能构成三角形，需要满足任意两边之和要大于第三边。但是实际上只需让较小的两条边之和大于第三边即可。
因此我们可以先将原数组排序，然后从小到大枚举三元组，一方面省去枚举的数量，另一方面方便判断是否能构成三角形。
第二种解法就是——双指针
根据「解法一」中的优化思想，我们可以固定一个「最长边」，然后在比这条边小的有序数组中找出一个二元组，使这个二元组之和大于这个最长边。由于数组是有序的，我们可以利用**「对撞指针」来优化。
先给数组排序，然后从右边开始指定一个数**，再在这个数的左边区间定义 left 和 right 指针进行对撞
如果 nums[left] + nums[right] > nums[i] ：说明 [left, right - 1] 区间上的所有元素均可以与 nums[right] 构成比nums[i] 大的二元组
满足条件的有 right - left 种
此时 right 位置的元素的所有情况相当于全部考虑完毕， right-- ，进入下一轮判断
如果 nums[left] + nums[right] <= nums[i] ：
说明 left 位置的元素是不可能与 [left + 1, right] 位置上的元素构成满足条件的二元组
left 位置的元素可以舍去， left++ 进入下轮循环
话不多说上代码吧
class Solution
{
public:
int triangleNumber(vector<int>& nums)
{
sort(nums.begin(),nums.end());
int ret = 0, n = nums.size();
for(int i = n - 1; i >= 2; i--)
{
int left = 0, right = i - 1;
while(left < right)
{
if(nums[left] + nums[right] > nums[i])
{
ret += right - left;
right--;
}
else
{
left++;
}
}
}
return ret;
}
};
查找总价格为目标值的两个商品
思路
解法一肯定还是暴力解法，但是超时是不可避免的
就是两层for循环遍历就好啦
解法二我们使用双指针
初始化 left ， right 分别指向数组的左右两端（这里不是我们理解的指针，而是数组的下标）
当 left < right 的时候，一直循环
当 nums[left] + nums[right] == target 时，说明找到结果，记录结果，并且返回；
当 nums[left] + nums[right] < target 时：
对于 nums[left] 而言，此时 nums[right] 相当于是 nums[left] 能碰到的最大值（别忘了，这里是升序数组哈~）。如果此时不符合要求，说明在这个数组里面，没有别的数符合 nums[left] 的要求了（最大的数都满足不了你，你已经没救了）。
因此，我们可以大胆舍去这个数，让 left++ ，去比较下一组数据；
那对于 nums[right] 而言，由于此时两数之和是小于目标值的， nums[right]还可以选择比 nums[left] 大的值继续努力达到目标值，因此 right 指针我们按兵不动；
当 nums[left] + nums[right] > target 时，同理我们可以舍去nums[right] （最小的数都满足不了你，你也没救了）。让 right-- ，继续比较下一组数据，而 left 指针不变（因为他还是可以去匹配比 nums[right] 更小的数的）
其实和上一题差不多，相对来说比较简单
话不多说，上代码
class Solution
{
public:
vector<int> twoSum(vector<int>& price, int target)
{
int left = 0, right = price.size()-1;
while(left < right)
{
int sum = price[left] + price[right];
if(sum == target)
return {price[left],price[right]};
else if(sum > target)
right--;
else
left++;
}
return {-1,-1};
}
};
两数之和
思路
其实和上一题差不多的，就是初始化 left 和 right 两个指针
然后对撞找出 numbers[left] + numbers[right] == target 的两个数就好啦
话不多说，上代码
class Solution
{
public:
vector<int> twoSum(vector<int>& numbers, int target)
{
int left = 0, right = numbers.size() - 1;
while(left < right)
{
if(numbers[left] + numbers[right] > target)
{
right--;
}
else if(numbers[left] + numbers[right] < target)
{
left++;
}
else
{
return {left + 1, right + 1};
}
}
return {-1, -1};
}
};
三数之和
思路
本题与两数之和类似，与两数之和稍微不同的是，题目中要求找到所有「不重复」的三元组。
那我们可以利用在两数之和（上一题）那里用的双指针思想，来对我们的暴力枚举做优化：
先排序；
然后固定一个数 a ：
在这个数后面的区间内，使用「双指针算法」快速找到两个数之和等于 -a 即可。但是要注意的是，这道题里面需要有**「去重」操作**~
找到一个结果之后， left 和 right 指针要「跳过重复」的元素；
当使用完一次双指针算法之后，固定的 **a 也要「跳过重复」**的元素。
思路比较简单，但是代码还是有点多
class Solution
{
public:
vector<vector<int>> threeSum(vector<int>& nums)
{
vector<vector<int>> ret;
int n = nums.size();
sort(nums.begin(),nums.end());
for(int i = 0; i < n; )
{
if(nums[i] > 0) break;
int left = i + 1, right = n - 1, target = -nums[i];
while(left < right)
{
int sum = nums[left] + nums[right];
if(sum > target)
right--;
else if(sum < target)
left++;
else
{
ret.push_back({nums[i], nums[left], nums[right]});
left++,right--;
while(left < right && nums[left - 1] == nums[left]) left++;// 去重
while(left < right && nums[right + 1] == nums[left]) right--; // 去重
}
}
i++;
while(i < n && nums[i] == nums[i - 1]) i++;// 去重处理
}
return ret;
}
};
四数之和
思路
和上题差不多的，就是加了一个数而已啦
依次固定一个数 a ；
在这个数 a 的后面区间上，利用「三数之和」找到三个数，使这三个数的和等于 target- a 即可
class Solution
{
public:
vector<vector<int>> fourSum(vector<int>& nums, int target)
{
int n = nums.size();
vector<vector<int>> ret;
sort(nums.begin(), nums.end());
for(int i = 0; i < n; )
{
for(int j = i + 1; j < n; )
{
int left = j + 1, right = n - 1;
long long aim = (long long)target - nums[i] - nums[j];
while(left < right)
{
int sum = nums[left] + nums[right];
if(sum < aim) left++;
else if(sum > aim)right--;
else
{
ret.push_back({nums[i], nums[j], nums[left], nums[right]});
left++, right--;
while(left < right && nums[left - 1] == nums[left]) left++;
while(left < right && nums[right + 1] == nums[right]) right--;
}
}
j++;
while(j < n && nums[j] == nums[j - 1]) j++;
}
i++;
while(i < n && nums[i] == nums[i - 1])i++;
}
return ret;
}
};
总结
今天对双指针有了新的理解，每一题的练习都是堆知识更加一步的理解
小编将持续不断为大家更新算法题，以及算法知识
一起加油呀~~~~~
