目前做美术的网站以及app,程序员接外包平台,广州网站开发怎么做,网页设计版式教程#x1f525;个人主页#xff1a;Quitecoder
#x1f525;专栏#xff1a;算法笔记仓 朋友们大家好啊#xff0c;本篇文章我们来到算法的双指针的第二部分 目录 1.有效三角形的个数2.查找总价格为目标值的两个商品3.三数之和4.四数之和5.双指针常见场景总结 1.有效三角形…
个人主页Quitecoder
专栏算法笔记仓 朋友们大家好啊本篇文章我们来到算法的双指针的第二部分 目录 1.有效三角形的个数2.查找总价格为目标值的两个商品3.三数之和4.四数之和5.双指针常见场景总结 1.有效三角形的个数 题目链接611. 有效三角形的个数 题目描述 这道题当然可以暴力求解三层循环枚举所有情况来进行判断但是可以进行优化
我们知道三角形的满足条件是任意的两边之和大于第三边但是如果我们已经判断了较小的两个边大于第三边就不需要再进行剩下两组的判断所以我们先进行排序再进行枚举
class Solution {
public:int triangleNumber(vectorint nums) {sort(nums.begin(),nums.end());}
};具体讲解一下我们的思路
这里使用的是一种双指针技术固定最长的边也就是数组中的最大值使用两个指针来查找剩余部分中可能的两个较短边。如果找到了两个较短边的长度和大于最长边那么这三者能构成一个三角形
class Solution {
public:int triangleNumber(vectorint nums) {sort(nums.begin(),nums.end());int count0;for(int inums.size()-1;i2;i--){int lati-1,pre0;while(prelat){if(nums[pre]nums[lat]nums[i]){countlat-pre;lat--;}else pre;}}return count;}
};它利用了一个重要的性质如果你有三条边长分别为 a, b 和 c且 a ≤ b ≤ c那么 a, b 和 c 可以构成一个三角形当且仅当 a b c
步骤如下
对数组 nums 进行升序排序初始化计数器 count 为 0从后往前遍历数组从最大值开始下标为 i我们将这个值作为潜在的最长边 c对于每一个 c设置两个指针pre 指针指向数组的开始下标为 0lat 指针指向 c 之前的元素下标为 i - 1当 pre 指针小于 lat 指针时 计算 nums[pre] 和 nums[lat] 的和将这个和与 nums[i]也就是当前的 c进行比较如果 nums[pre] nums[lat] nums[i]由于数组已经排序所有在 pre 和 lat 之间的元素与 nums[lat] 的和都会大于 nums[i]所以我们可以将 lat - pre 个三角形加到 count 上然后将 lat 向左移动一位减小一点以寻找下一个可能的三角形如果和小于等于 nums[i]我们将 pre 向右移动一位增大一点以寻找可能的三角形 当处理完所有的 c 后返回 count 作为结果
本道题还是很简单的
2.查找总价格为目标值的两个商品 题目链接LCR 179.查找总价格为目标值的两个商品 题目描述 算法的具体思路
初始化两个指针pre 指向数组的开始索引 0last 指向数组的末尾索引 price.size() - 1
vectorint s1;
int lastprice.size()-1;
int pre0;进行一个 while 循环在数组两端移动 pre 和 last 指针直到它们相遇。循环的条件是 pre last确保没有重复使用相同的元素。 在每次循环中计算两个指针指向的数的和判断这个和与目标值 target 的关系 如果和大于 target那么为了减小和last 指针左移减小索引值如果和小于 target那么为了增大和pre 指针右移增加索引值如果和等于 target 将这两个数添加到结果 vector s1 中。因为只需要一组解所以找到一对满足条件的数之后通过 break 语句退出循环
while(prelast)
{if(price[pre]price[last]target)last--;else if(price[pre]price[last]target)pre;else {s1.push_back(price[pre]);s1.push_back(price[last]);break;}
}返回结果 vector。如果找到至少一对和为 target 的数s1 会包含这两个数。如果没有找到s1 将是空的
完整代码如下
class Solution {
public:vectorint twoSum(vectorint price, int target) {vectorint s1;int lastprice.size()-1;int pre0;while(prelast){if(price[pre]price[last]target)last--;else if(price[pre]price[last]target)pre;else {s1.push_back(price[pre]);s1.push_back(price[last]);break;}}return s1;}
};3.三数之和 题目链接15.三数之和 题目描述 对于三数之和我们大思路如下
对于示例 我们首先进行排序 然后首先固定第一个数只需要在后面的数中找到两个数使三个数相加和为0即可
对于后面的数的寻找我们可以设置前后指针如果三数之和大于零则让较大的数减小点即右指针左移三数之和小于零则让左指针右移如果等于零则讲这三个数据插入到目标数组中继续遍历
注意上面的{-101}这三个数是可以构成目标数的但是必须跳过其中一个-1因为不能重复
class Solution {
public:vectorvectorint threeSum(vectorint nums) {vectorvectorint result;sort(nums.begin(),nums.end());for(int i0;inums.size()-2;i){if(i0nums[i-1]nums[i])continue;int prei1,lasnums.size()-1;while(prelas){if(nums[pre]nums[las](-nums[i]))pre;else if(nums[pre]nums[las](-nums[i]))las--;else{result.push_back({nums[i],nums[pre],nums[las]});while(prelasnums[pre1]nums[pre])pre;while(prelasnums[las-1]nums[las])las--;pre;las--;}}}return result;}
};注意的要点 唯一性返回的结果中不能包含重复的三元组。解决方法是在找到一个符合条件的组合后跳过所有相同的元素 遍历策略外层循环遍历数组内层使用双指针从两端向中间查找两个其他元素以保证三个数的和为零 跳过重复元素
在外层循环中如果当前的数字与前一个数字相同则跳过以避免重复的三元组 for(int i0;inums.size()-2;i)
{if(i0nums[i-1]nums[i])continue;在找到一个满足条件的三元组之后同时跳过 pre 指针的连续重复数字并将 pre 指针向右移动同样地跳过 las 指针的连续重复数字并将 las 指针向左移动 寻找条件三数之和等于零。这意味着在内层循环中如果 nums[pre] nums[las] 小于 -nums[i]则需要右移 pre 指针如果大于 -nums[i]则需要左移 las 指针如果等于 -nums[i]则记录该三元组继续寻找其他可能的组合 边界条件 外层循环的循环变量 i 应小于 nums.size() - 2因为需要至少3个数来组成一个三元组当 pre 和 las 指针相遇时内层循环结束。
我们还可以进一步优化当i对应的数字大于零意味着无论如何结果都大于零就可以直接break了
for(int i0;inums.size()-2;i)
{if(i0nums[i-1]nums[i])continue;if(nums[i]0)break;4.四数之和 题目链接18.四数之和 题目描述 这道题与上面三数求和大体思路一样我们这次一次固定两个数然后再遍历剩下的数遇见相同的数就往后移动
注意 上道题数组长度是大于等于3的而这道题nums数组长度大于等于1意味着可能不存在四个数所以首先我们先判断数组长度如果小于四直接返回空数组
if(nums.size()4)return{};首先进行排序工作
接着开始完成函数内容需要固定两个数我们则需要嵌套两个循环注意边界值即可
vectorvectorint result;
sort(nums.begin(), nums.end());
for(int i 0; i nums.size()-3; i) {if (i 0 nums[i] nums[i - 1]) continue; for (int j i 1; j nums.size()-2; j) {if (j i 1 nums[j] nums[j - 1]) continue; ——————————
}这里处理逻辑与上面一样先跳过相同的数在j的循环中我们就进行和上面相同的操作了
int pre j 1;
int last nums.size() - 1;
while (pre last) {long long sum (long long)nums[i] nums[j] nums[pre] nums[last]; if (sum target) {pre;}else if (sum target) {last--;}else {result.push_back({ nums[i], nums[j], nums[pre], nums[last] });while (pre last nums[pre] nums[pre 1]) pre; while (pre last nums[last] nums[last - 1]) last--; pre;last--;}
}本题还有一个关键点 它提供的值不一定是整形所以上面函数中我们使用长整型来避免溢出
总代码如下
class Solution {
public:vectorvectorint fourSum(vectorint nums, int target) {if (nums.size() 4)return{};vectorvectorint result;sort(nums.begin(), nums.end());for (int i 0; i nums.size() - 3; i) {if (i 0 nums[i] nums[i - 1]) continue; for (int j i 1; j nums.size() - 2; j) {if (j i 1 nums[j] nums[j - 1]) continue; int pre j 1;int last nums.size() - 1;while (pre last) {long long sum (long long)nums[i] nums[j] nums[pre] nums[last];if (sum target) {pre;}else if (sum target) {last--;}else {result.push_back({ nums[i], nums[j], nums[pre], nums[last] });while (pre last nums[pre] nums[pre 1]) pre;while (pre last nums[last] nums[last - 1]) last--;pre;last--;}}}}return result;}
};5.双指针常见场景总结
双指针主要应用在有序数组或链表的问题中以及一些可以通过前后关系来优化问题的场景 有序数组的对撞指针 两数之和在有序数组中找到两个数使它们的和为特定的目标值三数之和/四数之和与两数之和类似但需要找到三个或四个数的组合移除元素从有序数组中移除重复项或特定值并返回新数组的长度 快慢指针 链表中环的检测使用快慢指针检测链表是否有环快指针一次移动两步慢指针一次移动一步寻找链表中点使用快慢指针找到链表的中间节点快指针结束时慢指针在中点寻找链表的倒数第k个元素快指针先移动k步然后快慢指针共同移动快指针到达末尾时慢指针所在位置即倒数第k个元素 前后指针 归并排序中的合并步骤使用两个指针分别指向两个有序数组的开始位置以合并成一个新的有序数组。对链表进行操作在链表上进行操作时如删除节点或反转链表常常需要前后指针来保持结点的连接。 左右指针 二分查找在有序数组中查找元素使用左右指针限定查找范围
双指针方法的关键在于指针的移动可以依据问题的规律来减少不必要的比较或计算从而提高算法效率。当然双指针的使用需要充分理解问题的性质并巧妙设计指针的移动策略。在很多问题中双指针技术都能将时间复杂度从 O(n2) 优化到 O(n),超级好用
本节内容到此结束感谢大家阅读
