建立网站的准备工作,外贸网站建设公司市场,深圳响应式建站,为什么自己做的网站用QQ打不开大厂算法指南#xff1a;优选算法 ——双指针篇#xff08;上#xff09; 前言#xff1a;双指针简介一、[611. 有效三角形的个数](https://leetcode.cn/problems/valid-triangle-number/)1.1 算法思路#xff08;排序 双指针#xff09;1.2 代码实现 二、[LCR 179. 查找… 大厂算法指南优选算法 ——双指针篇上 前言双指针简介一、[611. 有效三角形的个数](https://leetcode.cn/problems/valid-triangle-number/)1.1 算法思路排序 双指针1.2 代码实现 二、[LCR 179. 查找总价格为目标值的两个商品](https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof/)2.1 算法思路2.2 代码实现 三、[15. 三数之和](https://leetcode.cn/problems/3sum/)3.1 算法思路3.2 代码实现 四、[18. 四数之和](https://leetcode.cn/problems/4sum/)4.1 算法思路排序 双指针4.2 代码实现 作者简介非科班在读纯技术博客分享致力于C/C涉及Python、C/C、Linux,数据结构git企业级开发Mysql等。 本文收录于算法指南旨在帮助读者应对各大互联网大厂笔试题构建完整的算法体系 相关专栏C语言、C、数据结构、Linux、前言科技喜欢C/C/Linux/算法的朋友们可以关注一下哦 ———————————————— 版权声明本文为CSDN博主「小宇成长录」的原创文章遵循CC 4.0 BY-SA版权协议转载请附上原文出处链接及本声明。 原文链接https://editor.csdn.net/md/?not_checkout1spm1011.2124.3001.6183 前言双指针简介
常⻅的双指针有两种形式⼀种是对撞指针⼀种是左右指针。 对撞指针⼀般⽤于顺序结构中也称左右指针。 。对撞指针从两端向中间移动。⼀个指针从最左端开始另⼀个从最右端开始然后逐渐往中间逼近。 。对撞指针的终⽌条件⼀般是两个指针相遇或者错开也可能在循环内部找到结果直接跳出循环也就是 ◦ left right 两个指针指向同⼀个位置 ◦ left right 两个指针错开 快慢指针⼜称为⻳兔赛跑算法其基本思想就是使⽤两个移动速度不同的指针在数组或链表等序列结构上移动。 这种⽅法对于处理环形链表或数组⾮常有⽤。其实不单单是环形链表或者是数组如果我们要研究的问题出现循环往复的情况时均可考虑使⽤快慢指针的思想。 快慢指针的实现⽅式有很多种最常⽤的⼀种就是 。 在⼀次循环中每次让慢的指针向后移动⼀位⽽快的指针往后移动两位实现⼀快⼀慢。 话不多说现在来看看大厂们比较有代表性的面试题吧
一、611. 有效三角形的个数 1.1 算法思路排序 双指针
先将数组排序。 我们可以固定⼀个「最⻓边」然后在⽐这条边⼩的有序数组中找出⼀个⼆元组使这个⼆元组之和⼤于这个最⻓边。由于数组是有序的我们可以利⽤「对撞指针」来优化。
设最⻓边枚举到 i 位置区间 [left, right] 是 i 位置左边的区间也就是⽐它⼩的区间 如果 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 进⼊下轮循环。
1.2 代码实现
class Solution {
public:int triangleNumber(vectorint nums) {sort(nums.begin(), nums.end());//排序int ret0;for(int inums.size()-1; i2; i--){int left0, righti-1, targetnums[i];while(leftright){if(nums[left] nums[right] target){ret right-left;right--;}else{left;}}}return ret;}
};二、LCR 179. 查找总价格为目标值的两个商品
(https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof/)
2.1 算法思路
注意到本题是升序的数组因此可以⽤「对撞指针」优化时间复杂度。
算法流程如下
初始化 left right 分别指向数组的左右两端这⾥不是我们理解的指针⽽是数组的下标当 left right 的时候⼀直循环以下过程 1.当 nums[left] nums[right] target 时说明找到结果记录结果并且返回 2.当 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] 更⼩的数。
2.2 代码实现
class Solution {
public:vectorint twoSum(vectorint price, int target) {int left0, rightprice.size()-1;while(leftright){if(price[left] price[right] target)right--;else if(price[left] price[right] target)left;elsereturn {price[left], price[right]};}return {-1, -1};}
};三、15. 三数之和 3.1 算法思路
本题与两数之和类似是⾮常经典的⾯试题。 与两数之和稍微不同的是题⽬中要求找到所有「不重复」的三元组。那我们可以利⽤在两数之和那⾥⽤的双指针思想来对我们的暴⼒枚举做优化
先排序然后固定⼀个数 a 在这个数后⾯的区间内使⽤「双指针算法」快速找到两个数之和等于 -a 即可。
但是要注意的是这道题⾥⾯需要有「去重」操作~
找到⼀个结果之后 left 和 right 指针要「跳过重复」的元素’当使⽤完⼀次双指针算法之后固定的 a 也要「跳过重复」的元素
3.2 代码实现
class Solution {
public:vectorvectorint threeSum(vectorint nums) {vectorvectorint ret;//1. 排序sort(nums.begin(), nums.end());//2. 双指针思路for(int inums.size()-1; i2; i--){if(nums[i]0)break;int left 0, righti-1;while(leftright){if(nums[left] nums[right] nums[i] 0)right--;else if(nums[left] nums[right] nums[i] 0)left;else{//相等,记录数据处理相同元素ret.push_back({nums[left], nums[right], nums[i]});left, right--;//处理相同元素while(leftright nums[left-1] nums[left]){left;}while(leftright nums[right1] nums[right]){right--;}}//处理相同元素防止重叠while(i 2 nums[i] nums[i-1]){i--;}}}return ret;}
};四、18. 四数之和 4.1 算法思路排序 双指针
a. 依次固定⼀个数 a b. 在这个数 a 的后⾯区间上利⽤「三数之和」找到三个数使这三个数的和等于 target - a 即可。
4.2 代码实现
lass Solution
{
public:vectorvectorint fourSum(vectorint nums, int target) {vectorvectorint ret;// 1. 排序sort(nums.begin(), nums.end());// 2. 利⽤双指针解决问题int n nums.size();for(int i 0; i n; ) // 固定数 a{// 利⽤ 三数之和for(int j i 1; j n; ) // 固定数 b{// 双指针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--]});// 去重⼀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;}
};
