【优选算法】Pointer-Slice：双指针的算法切片（下）
文章目录
- 1.有效三角形的个数
- 2.查找总价格为目标值的两个商品
- 3.三数之和
- 4.四数之和
- 希望读者们多多三连支持
- 小编会继续更新
- 你们的鼓励就是我前进的动力！
本篇接上一篇双指针算法，继续处理剩下的经典题目
1.有效三角形的个数
✏️题目描述：
✏️示例：
传送门：有效三角形的个数
题解:
💻第一步：
一般针对三元的变量，优先想到的是三层 for 循环暴力枚举所有的组合，此时的时间复杂度为O(n³)，明显是超时了。争取遍历一遍就能找出所有组合，那么就要减少无效的枚举
根据数学知识可知，假设三角形最大边为c，那么其余两边a、b之和大于c，就能确定一个三角形
为了减少无效的枚举，通常需要利用数列的单调性，就用sort函数迭代器对数组升序排序
💻第二步：
由于是三元，且依据数学知识，我们先固定其中一个数(从最大的开始)，剩下两个数就可以利用双指针求组合
假设两数之和大于c，那么可以减小和，寻找是否还有符合要求的组合，即right--；假设两数之和小于c，那么需要增加和，寻找有符合要求的组合，即left++；和相等时就返回组合，然后继续left++，因为减小和仍然有可能找到符合大于c的组合。每判断一次和，就要执行一次移动，当left >= right就停止，此时最大数的组合情况已经全部找完，接下来c就减小一位，继续循环上述操作
注意c最多减小到索引为2的位置，保证依然为三元组合
💻代码实现:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
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;
}
};
2.查找总价格为目标值的两个商品
✏️题目描述：
✏️示例：
传送门：查找总价格为目标值的两个商品
题解:
💻细节问题：
该题是上一题的简化版，显然是使用双指针找符合的组数
唯一不同的是上题要寻找所有符合的情况，该题找到一个符合的即可
💻代码实现:
#include <iostream>
#include <vector>
using namespace std;
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)
{
left++;
}
else if (sum > target)
{
right--;
}
else return { price[left], price[right] };
}
return{ -1,-1 };
}
};
3.三数之和
✏️题目描述：
✏️示例：
传送门：三数之和
题解:
本题也是三元组合的问题，与有效三角形的个数那题的思路也是一样的，做到不漏情况是很简单的，但是本题要求不重复，那么这是本题要处理的难点，细节问题特别多
💻第一步： 不漏
或许可以通过暴力枚举+set容器去重，但仍然涉及时间复杂度高的问题，所以还是排序+双指针的方法减小时间复杂度
💻第二步： 不重
🚩left、right不重复
🚩固定的数不重复
因为此时其余两个数都是不变的，移动到下一个一样的数重复了之前的情况，为了减少不必要的枚举，当遇到重复的数时两种情况都需要跳过
💻细节问题：
注意不要在处理重复数的情况时移动越界，要考虑如果都是重复数的情况
💻代码实现:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution
{
public:
vector<vector<int>> threeSum(vector<int>& nums)
{
sort(nums.begin(), nums.end());
int n = nums.size();
vector<vector<int>> ret;
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)
{
left++;
}
else if(sum > target)
{
right--;
}
else
{
ret.push_back({ nums[i],nums[left],nums[right] });
left++, right--;
while (left < right && nums[left] == nums[left - 1])
{
left++;
}
while (left < right && nums[right] == nums[right + 1])
{
right--;
}
}
}
i++;
while (i < n && nums[i] == nums[i - 1])
{
i++;
}
}
return ret;
}
};
4.四数之和
✏️题目描述：
✏️示例：
传送门：四数之和
💻细节问题：
四数之和和三数之和是一个思路，只不过是要固定两个数，套用两层 for 循环处理两次边界问题，注意双指针运算过程中，比较的值可能会太大，所以要用 long long
💻代码实现:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution
{
public:
vector<vector<int>> fourSum(vector<int>& nums, int target)
{
sort(nums.begin(), nums.end());
int n = nums.size();
vector<vector<int>> ret;
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] == nums[left - 1])
{
left++;
}
while (left < right && nums[right] == nums[right + 1])
{
right--;
}
}
}
j++;
while (j < n && nums[j] == nums[j - 1])
{
j++;
}
}
i++;
while (i < n && nums[i] == nums[i - 1])
{
i++;
}
}
return ret;
}
};
寒冷的冬夜里，祝大家圣诞节快乐，平安喜乐！🎅❄️🎄
希望读者们多多三连支持
小编会继续更新
你们的鼓励就是我前进的动力！
