文章目录 一、双指针算法分类 二、相向双指针示例 ( 有效回文串 ) 一、双指针算法分类 ---- 面试时经常遇到 限制算法复杂度为 O ( n ) 的情况 , 就需要使用以下算法 : 双指针算法...: 设置两个指针 ( 索引 ) , 进行不同方式的遍历 , 使用最高频的算法 ; 打擂台算法 : 设置一个擂主值 , 设置为无穷大或无穷小 , 通过遍历让该擂主值与遍历值打擂台 ; 求最大值最小值常用...; 单调栈算法 ; 单调队列算法 ; 双指针算法分类 : 相向双指针 : 判断一个字符串是否是回文串 , 从两边向中心遍历 ; 背向双指针 : 查找一个字符串的最长回文子串使用的 " 中心线枚举算法 "...就是背向双指针算法 , 从中心向两边遍历 ; ( 出现频率较 - 低 ) 同向双指针 : 相向双指针算法分类 : 翻转类型 : ① 翻转字符串 , ② 判断回文串 ; 两个指针分别指向收尾 , 两边往中间走...然后对比是否相等 ; 但是如果添加了上述要求 , 就需要处理大小写 , 特殊字符问题 , 有两种方案 : 创建新字符串 , 过滤掉大小写及特殊字符干扰, 然后翻转字符对比 , 这样会增加额外空间开销 ; 推荐使用双指针算法
二、算法原理 如果用双指针从前往后遍历，就拿例1来说， 就会出现值被覆盖的情况： 所以遍历顺序就不能从前往后。...可以先用双指针算法：1.先判断cur位置；2.决定dest向后移动一步或者两步；3.判断一下dest是否已经到达结束位置；4.在把cur加加。...二、算法原理 利用数组是有序的，用双指针算法来算。 定义两个指针，一个在左边，一个在右边。...二、算法原理 排序之后，数据是有序的，这里就用双指针算法。...这里是三个数的和，可以先固定一个数a，仅想要保证这个a是小于0就行（在后面等于0相加的值不可能等于0），然后在该数后面的区间内，利用双指针算法，快速找到两个数的和，者两个数的和是a的相反数，这样这三个数相加的时候
双指针 双指针是一种思想或一种技巧并不是特别具体的算法。具体就是用两个变量动态存储两个结点，来方便我们进行一些操作。通常用在线性的数据结构中。...特别是链表类的题目，经常需要用到两个或多个指针配合来记忆链表上的节点，完成某些操作。 常见的双指针方式 •同速指针：链表上两个指针，一个先出发，另一个后出发并以相同的速度跟随。...•求链表的逆：通过临时指针让双指针同步前行•求链表倒数第k个元素：先让其中一个指针向前走k步，接着两个指针以同样的速度一起 向前进，直到前面的指针走到尽头了，则后面的指针即为倒数第k个元素 •快慢指针：...双指针常用于线性结构：链表，数组 例题 151.反转链表 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。...输出：[1,2] 示例 2： 输入：head = [1,1,2,3,3] 输出：[1,2,3] 解题思路： •方法1：使用栈的思想，如果后面入的元素与栈顶元素相同，就略过该元素，继续遍历•方法2：双指针
双指针 双指针 常见的双指针有两种形式，⼀种是对撞指针，⼀种是左右指针。 对撞指针：⼀般用于顺序结构中，也称左右指针。 对撞指针从两端向中间移动。...快乐数 题目链接 -> Leetcode -202.快乐数 Leetcode -202.快乐数 题目：编写一个算法来判断一个数 n 是不是快乐数。...那我们可以利用在两数之和那里用的双指针思想，来对我们的暴力枚举做优化： i. 先排序； ii. 然后固定⼀个数 a ： iii....在这个数后⾯的区间内，使用「双指针算法」快速找到两个数之和等于 -a 即可。 但是要注意，这道题里面需要有「去重」操作： i....当使用完⼀次双指针算法之后，固定的 a 也要「跳过重复」的元素 代码如下： class Solution { public: vector> threeSum
2、原地对数组进行操作 思路：双指针算法 class Solution { public: void moveZeroes(vector& nums) {...思路：双指针算法 class Solution { public: void duplicateZeros(vector& arr) { int cur=0,des...} } }; 三、快乐数 . - 力扣（LeetCode）快乐数 该题的关键是：将正整数变成他的每位数的平方之和，有可能会一直循环始终到不了1，也有始终是1（快乐数） 思路：快慢双指针算法...j) ret=max(ret,min(height[i],height[j])*(j-i)); return ret; } }; 思路2、双指针对撞算法...right; } return ret; } }; 五、有效三角形的个数 . - 力扣（LeetCode）有效三角形的个数 思路1：升序+暴力枚举 思路2：升序+利用双指针算法
基础算法篇——双指针算法 本次我们介绍基础算法中的双指针算法，我们会从下面几个角度来介绍： 双指针简介 双指针基本使用 最长连续不重复字符列 数组元素的目标和 判断子序列 双指针简介 首先我们先来简单介绍一下双指针...： 双指针算法就是采用两个变量作为指针放在数组的某个部位来实现复杂度简化 我们来介绍一下双指针的使用场景： 双指针通常用于简化双for循环的场景，将复杂度为O(N^2)变为O(N) 双指针可以用于单个序列中...，例如我们之前的快速排序所使用的双指针算法 双指针可以用于多个序列中，例如我们之前的归并排序所使用的双指针算法 我们的双指针算法通常是由双for的暴力求解优化得来的： // 双for循环O(n^2)...里面装有一些单词，单词由空格隔开，我们需要将他们单独打出来 思路解释： /* 我们采用双指针算法 i指针指向单词的第一个字母，j指向单词后面的空格，我们只需要输出i和j-1之前的字母并隔开即可 */ 算法实现...}else { System.out.println("不是子序列"); } return; } } 结束语 好的，关于基础算法篇的双指针算法就介绍到这里
输入有序数组(https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/) 长按复制到浏览器即可到leetcode对应的题目， 算法的逻辑在具体的代码注释里...* * 思路： * 使用双指针，一个指针指向值较小的元素，一个指针指向值较大的元素。 * 指向较小元素的指针从头向尾遍历，指向较大元素的指针从尾向头遍历。...* 如果两个指针指向元素的和 sum == target，那么得到要求的结果； * 如果 sum > target，移动较大的元素，使 sum 变小一些； * 如果 sum < target，移动较小的元素...* 快慢指针 * 使用双指针，一个指针每次移动一个节点，一个指针每次移动两个节点，如果存在环，那么这两个指针一定会相遇。...* * 通过删除字符串 s 中的一个字符能得到字符串 t，可以认为 t 是 s 的子序列， * 我们可以使用双指针来判断一个字符串是否为另一个字符串的子序列。
双指针分类 快慢指针 左右指针 快慢指针：主要解决链表相关问题，比如：典型的判断链表中是否包含环、链表倒是第K个节点等 左右指针：主要解决数组（或者字符串）中的问题：比如：二分查找 快慢指针 题目：...later = later->next; first = first->next; } return later; } 左右指针
双指针算法是指的在遍历过程中，我们给定两个指针在相同或者相向方向遍历，在数组有序的情况下，使我们的算法复杂度降低。 【经典题目1-两数之和】 相向指针，比如leetcode中的167题。 ?...这样两个指针改为同向遍历即可实现。
一、什么叫做双指针算法？...双指针是一种方法，一种思想一种技巧，也谈不上什么特别的算法，在二分查找中经常使用这个技巧，具体就是用两个变量动态的存储两个或者多个的结点，来方便我们进行一些操作，通常使用在线性结构中，比如说数组或者是链表...在我们遇到像数组，链表这类数据结构的算法题目的时候，应该要想得到双指针的来解决问题。特别是链表类的题目，经常需要用到两个或多个指针配合来记忆链表上的节点，完成某些操作。...链表这种数据结构也是树形结构和图的原型，所以有时候在关于图和树形结构的算法题目中也会用到双指针。...这个题目比较简单，不需要用到双指针，一般在用双指针的时候，需要有序数组，先排序。这题目有几种思路，首先我想到的就是利用暴力方法，直接算。看代码： 嵌套循环 -> 第二层为什么是i+1开始呢？
双指针算法模板： for (int i = 0, j = 0; i < n; i ++ ) { while (j < i && check(i, j)) j ++ ;...// 具体问题的逻辑 } 常见问题分类： (1) 对于一个序列，用两个指针维护一段区间 (2) 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作 最长连续不重复子序列
一、题目分类 双指针目前LC上涉及83道题，属于面试的一个高频范围区。我们根据标签分类是可以获取到一部分信息笔试考察范围点的。目前LC上一共是1989道题。...概率为83/1989= 4.17%. image.png 二、题目举例 链表中是否有环 查找、删除链表倒数第K个节点 最小覆盖子串 两数之和-有序数组 三数之和 最接近的三数之和 ....等 三、双指针的思想...双指针的思想可以归纳为： 双指针很奇妙，一快一慢走。...四、解题表达式 双指针公式->固定一方，变动另一方，或者双方一起同步 right = left + K; //链表倒数第K个节点类问题 while(right.next !.../固定右指针，移动左指针 if(condition2){ //处理使其满足condition1条件,并不符合condition2条件 left++; }
例题 1，反转链表（递归，双指针/迭代） 来自 LeetCode206 补充： * public class ListNode { * int val; * ListNode next...理解（不保证正确） 1，链表题应该在本子上画出过程，这样很容易得到算法。...now.next = temp; if(left==1) return pre; return head; } } 根据反转链表1的双指针算法写出...2，正向双指针 因为已经排好序，所以比较最小只需要比较最靠前的元素即可。 这里就能想到双指针，但是这个方法必须新建一个新数组，空间复杂度高。...正向双指针的逆想法 如果不想新建新数组的话，用最小覆盖可能会覆盖nums1原来的元素 所以我们可以想到用最大来覆盖，nums1最后的元素，因为nums1长度固定。
i < n; i ++ ) { while (j < i && check(i, j)) j ++ ; // 具体问题的逻辑 } 常见问题分类： (1) 对于一个序列，用两个指针维护一段区间
双指针算法 双指针算法的常见情况： 双指针在两个数组上（例如归并排序等等） 双指针在一个数组上 常见通用代码模板 for(i = 0, j =0; i < n; i++ ) {...常见的遍历一共是双重循环，复杂度是O( n^2 ) 但是双指针算法虽然是看起来是双重循环，但是实际上每个指针移动的次数是不超过O(n)的，两个指针的总次数不超过O(2n)。...基本思路：采用双指针算法 首先i和j在同一起点位置，然后j进行扫描。 j停在空格分界的位置上，输出两位置之间的字符串 把指针i移动在j上。...int j = 0; j < i; j++) if(chack(i,j)) { res = max(res, i - j +1); } } 双指针算法模板...注意：要想采用双指针算法优化，重要的是这一种单调关系。 数组元素的目标和 给定两个升序排序的有序数组 A 和 B，以及一个目标值 x。 数组下标从 0 开始。
✨博主：命运之光 ✨专栏：算法基础学习 前言：算法学习笔记记录日常分享，需要的看哈O(∩_∩)O，感谢大家的支持！...✨双指针 双指针算法的核心思想： for(int i=0;i<n;i++) for(int j=0;j<n;j++) O(n^2) 将上面的朴素算法优化到O(n) 双指针模板： for...= 0; i < n; i ++ ) { while (j < i && check(i, j)) j ++ ; // 具体问题的逻辑 } 常见问题分类： (1) 对于一个序列，用两个指针维护一段区间
解释 其实双指针算法，并不是一种具体的公式或者范式。而是一种思路。一种节省时间运算的思路。 通常是指通过设置两个指针不断进行单向移动来解决问题的形式。...双指针算法的核心用途就是：优化时间复杂度 而我们经常使用双指针的场景就是两层循环。 指针，其实就代表了我们循环过程中的下标值。 我们讲了，双指针只是一种思路。...而针对某些场景大家使用双指针总结了一些通用范例。 左右指针：创建两个指针（变量），一个指向开头，一个指向末尾，然后向中间遍历，直到满足条件或者两个指针相遇； 快慢指针：常见于链表查询中。...创建两个指针，开始都指向开头，根据条件不同，快指针走得快，慢指针走的慢，直到满足条件或者快指针走到结尾； 滑动窗口：进行单调性的子串问题。...ans = Math.max(ans, rk - i + 1); } return ans; } 就是一个典型的利用滑动窗口的思路，来实现的算法
文章目录 日志统计 一般做法 用双指针算法改进 日志统计 小明维护着一个程序员论坛。现在他收集了一份”点赞”日志，日志共有 N 行。...) st[id] = true; } } for( int i = 1; i <= 100000; i ++ ) { if(st[i]) cout << i <<endl; } 用双指针算法改进...%d%d", &logs[i].x, &logs[i].y); // 对pair进行排序, 排序时默认以first为准排序 sort(logs, logs + n); // 双指针算法.../ 如果俩个帖子时间相差超过d，说明该赞无效 { cnt[logs[j].y] -- ; // 所以此刻--； j ++ ; // 要把指针
算法 系列博客 【算法】刷题范围建议 和 代码规范 【算法】复杂度理论 ( 时间复杂度 ) 【字符串】最长回文子串 ( 蛮力算法 ) 【字符串】最长回文子串 ( 中心线枚举算法 ) 【字符串】最长回文子串...( 动态规划算法 ) ★ 【字符串】字符串查找 ( 蛮力算法 ) 【字符串】字符串查找 ( Rabin-Karp 算法 ) 【算法】双指针算法 ( 双指针算法分类 | 相向双指针 | 有效回文串...) 【算法】双指针算法 ( 有效回文串 II ) ---- 文章目录 算法 系列博客 一、有效回文串 II 一、有效回文串 II ---- 有效回文串 II : https://www.lintcode.com.../problem/891/ 给定非空字符串 , 最多删除一个字符 , 判断是否可以将该字符串变成回文串 ; 该算法是一个贪心算法 , 给定一个字符串 “abca” , 设置两个指针 , 分别指向最左侧字符...和 最右侧字符 , 从两端开始遍历 , 逐个比较两个指针指向的字符是否相等 ; 如果出现了左右指针指向的字符不相等 , 那么只能有两种操作 , 要么删除左指针指向的字符 , 要么删除右指针指向的字符
triangleNumber(vector& nums) { sort(nums.begin(),nums.end()); } }; 具体讲解一下我们的思路： 这里使用的是一种双指针技术...增大一点以寻找可能的三角形） 当处理完所有的 c 后，返回 count 作为结果 本道题还是很简单的 2.查找总价格为目标值的两个商品 题目链接：LCR 179.查找总价格为目标值的两个商品 题目描述： 算法的具体思路...双指针主要应用在有序数组或链表的问题中，以及一些可以通过前后关系来优化问题的场景： 有序数组的对撞指针： 两数之和：在有序数组中找到两个数，使它们的和为特定的目标值 三数之和/四数之和：与两数之和类似...左右指针： 二分查找：在有序数组中查找元素，使用左右指针限定查找范围 双指针方法的关键在于，指针的移动可以依据问题的规律来减少不必要的比较或计算，从而提高算法效率。...当然，双指针的使用需要充分理解问题的性质，并巧妙设计指针的移动策略。在很多问题中，双指针技术都能将时间复杂度从 O(n2) 优化到 O(n),超级好用 本节内容到此结束！！感谢大家阅读！！
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
ICP备案
实时音视频
即时通信 IM
对象存储
