双指针算法精解与应用

双指针算法双指针算法主要分为两种类型对撞指针和快慢指针。对撞指针左右指针适用于顺序结构从两端向中间移动初始化左指针从起始位置开始右指针从末尾位置开始终止条件指针相遇left right指针错开left right也可能在循环内部提前找到结果而跳出2.快慢指针龟兔赛跑算法通过两个不同速度的指针在序列结构上移动典型应用场景环形链表或数组检测任何存在循环往复模式的问题常见实现方式慢指针每次移动一步快指针每次移动两步下面这些问题我称之为数组分块1. 移动零easy「数组分两块」是⾮常常⻅的⼀种题型主要就是根据⼀种划分⽅式将数组的内容分成左右两部 分。这种类型的题⼀般就是使⽤「双指针」来解决。题目描述编写一个函数将给定数组nums中的所有零元素移至数组末尾同时保持非零元素的原始相对顺序。要求在原数组上进行操作不得创建数组副本。示例输入nums [0,1,0,3,12]输出[1,3,12,0,0]输入nums [0]输出[0]1. 题⽬链接https://leetcode.cn/problems/move-zeroes算法思路在本题中我们可以⽤⼀个 的最后⼀个位置。根据 cur 指针来扫描整个数组另⼀个 dest 指针⽤来记录⾮零数序列 cur 在扫描的过程中遇到的不同情况分类处理实现数组的划分。 在 cur 遍历期间使 [0, dest] 的元素全部都是⾮零元素 元素全是零。C算法代码// 移动零元素算法 class Solution { public: void moveZeroes(vectorint nums) { // 使用双指针法 for(int cur 0, dest -1; cur nums.size(); cur) { if(nums[cur] ! 0) { // 当遇到非零元素时 // 交换元素位置 swap(nums[dest], nums[cur]); } } } };2. 复写零easy1. 题⽬链接https://leetcode.cn/problems/duplicate-zeros题目描述给定一个固定长度的整数数组 arr要求将数组中出现的每个零元素复制一遍并将其他元素向右平移。注意修改后的元素不能超过原数组长度。请直接在原数组上进行修改不要返回任何内容。示例 输入arr [1,0,2,3,0,4,5,0] 输出[1,0,0,2,3,0,0,4] 说明调用函数后原数组将被修改为上述结果。解法双指针原地复写算法思路 [1,0,0,2,3,0,0,4] 如果「从前向后」进⾏原地复写操作的话由于 0 的出现会复写两次导致没有复写的数「被覆 盖掉」。因此我们选择「从后往前」的复写策略。 但是「从后向前」复写的时候为了不超过数组大小我们需要找到「最后⼀个复写的数」因此我们的⼤体流程分两 步i. 先找到最后⼀个复写的数ii. 然后从后向前进⾏复写操作。完成上面的算法操作我们提交代码会面临有些案例通不过这时候就要分析是否有临界情况。通过报错的测试用例反推可知dest会越界。判断 dest 是否越界到 n 的位置i. 如果越界执⾏下⾯三步1. n- 1 位置的值修改成 0 2. cur 向移动⼀步3. dest 向前移动两步。C算法代码class Solution { public: void duplicateZeros(vectorint arr) { int cur 0, dest -1; int n arr.size(); while (cur n) { if (arr[cur] 0) { dest 2; } else { dest; } if (dest n - 1) break; cur; } if (dest n) { arr[n - 1] 0; cur--; dest - 2; } while (cur 0) { if (arr[cur]) { arr[dest--] arr[cur--]; } else { arr[dest--] 0; arr[dest--] 0; cur--; } } } };3. 快乐数medium题目链接https://leetcode.cn/problems/happy-number题目描述编写一个算法判断给定数字 n 是否为快乐数。快乐数定义对于一个正整数将其替换为各位数字的平方和重复上述过程直到数字变为 1 或进入无限循环最终结果为 1 则为快乐数返回值若 n 是快乐数返回 true否则返回 false示例 1输入n 19输出true解释19 → 1² 9² 8282 → 8² 2² 6868 → 6² 8² 100100 → 1² 0² 0² 1算法思路为便于说明我们将对一个正整数将其替换为各位数字平方和这一操作记为x操作。题目指出重复执行x操作时必然会出现死循环且循环方式只有两种可能情况一陷入1的循环即1→1→1→1...情况二陷入非1的历史数据循环由于这两种情况互斥因此只需判断循环属于情况一还是情况二即可得出最终结论。通过上述分析可知重复执行x时数据会进入循环状态。快慢指针的特性在于在循环中快指针必定会追上慢指针并相遇。若相遇点的值为1则该数为快乐数反之则不是快乐数。C算法代码class Solution { public: // 计算数字各位的平方和 int bitSum(int n) { int sum 0; while (n 0) { int digit n % 10; sum digit * digit; n / 10; } return sum; } // 判断是否为快乐数 bool isHappy(int n) { int slow n; int fast bitSum(n); while (slow ! fast) { slow bitSum(slow); fast bitSum(bitSum(fast)); } return slow 1; } };4. 盛⽔最多的容器medium题⽬链接https://leetcode.cn/problems/container-with-most-water法一最简单直接暴力算法算出每一个值最后得出体积最大的值法二通过观察单调性可以发现当使用双指针向内遍历时长度会逐渐减小。此时若宽度也减小则可直接跳过该情况。int maxArea(vectorint height) { int left 0, right height.size() - 1; int ret 0; while (left right) { int v (right - left) * (min(height[left], height[right])); ret max(ret, v); if (height[left] height[right]) right--; else left; } return ret; }5. 有效三⻆形的个数medium题⽬链接https://leetcode.cn/problems/valid-triangle-number算法步骤排序数组 对输入数组进行升序排序以便利用有序性快速筛选有效组合。排序后较大的数字集中在数组右侧。固定最长边并双指针搜索 从数组末尾开始遍历将当前元素nums[i]作为潜在最长边。初始化双指针left0和righti-1在[left, right]范围内寻找满足nums[left] nums[right] nums[i]的组合。调整指针并统计结果 当nums[left] nums[right] nums[i]时说明从left到right-1的所有元素与nums[right]和nums[i]都能构成有效三角形因此直接累加right-left到结果中并右移right指针。否则左移left指针以增大和值。复杂度分析时间复杂度O(n^2)排序耗时 $O(n \log n)$双指针遍历耗时 $O(n^2)$总体以双指针部分为主。空间复杂度O(1)仅使用常数级别的额外空间。关键点说明三角形不等式对于排序后的数组若a ≤ b ≤ c只需满足a b c即可构成三角形。双指针优化通过固定c并动态调整a和b将暴力三重循环优化为双重循环。示例演示输入nums [2,2,3,4]的流程排序后数组为[2,2,3,4]。固定c4双指针初始为left0值2、right2值3。23 4成立累加2-02即组合(2,3,4)和(2,3,4)右移right。最终返回有效组合数3实际为(2,3,4)、(2,3,4)、(2,2,3)。class Solution { public: int triangleNumber(vectorint nums) { int count 0; sort(nums.begin(), nums.end()); for (int i nums.size() - 1; i 2; i--) { int left 0, right i - 1; while (left right) { if (nums[left] nums[right] nums[i]) { count right - left; right--; } else { left; } } } return count; } };6.和为s的两个数字easy题⽬链接https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof算法思路使用双重循环遍历所有可能的数字组合判断其和是否等于目标值。暴力会超时算法流程外层循环遍历第一个数a内层循环遍历第二个数b从a之后开始遍历优化说明由于a之前的组合已在先前迭代中考虑过因此内层循环只需遍历a之后的数字对每对组合(a,b)进行求和运算验证是否等于目标值class Solution { public: vectorint twoSum(vectorint price, int target) { int left 0, right price.size() - 1; while (left right) { int sum price[left] price[right]; if (sum target) { right--; } else if (sum target) { left; } else { return {price[left], price[right]}; } } return {-1, -1}; } };7. 三数之和medium题⽬链接https://leetcode.cn/problems/3sum本题与两数之和类似是一道非常经典的面试题。与两数之和稍有不同的是题目要求找到所有不重复的三元组。我们可以借鉴两数之和的双指针思路对暴力枚举进行优化首先对数组进行排序固定一个数a在该数后面的区间内使用双指针算法快速找到两个数之和等于-a需要注意去重操作找到符合条件的解后left和right指针需要跳过重复元素每次双指针算法执行完毕后固定的a也需要跳过重复元素class Solution { public: vectorvectorint threeSum(vectorint nums) { vectorvectorint result; 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; while (left right) { int sum nums[i] nums[left] nums[right]; if (sum 0) { result.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--; } else if (sum 0) { left; } else { right--; } } i; while (i n nums[i] nums[i - 1]) i; } return result; } };8.四数之和medium题⽬链接https://leetcode.cn/problems/4sum解法排序双指针算法思路固定一个基准数a在a后面的区间内运用三数之和的解法寻找三个数使其和等于target - aclass Solution { public: vectorvectorint fourSum(vectorint nums, int target) { sort(nums.begin(), nums.end()); int n nums.size(); vectorvectorint result; for (int i 0; i n - 3;) { for (int j i 1; j n - 2;) { int left j 1; int right n - 1; while (left right) { long long sum (long long)nums[i] nums[j] nums[left] nums[right]; if (sum target) { result.push_back({nums[i], nums[j], nums[left], nums[right]}); left; while (left right nums[left - 1] nums[left]) left; right--; while (left right nums[right 1] nums[right]) right--; } else if (sum target) { right--; } else { left; } } j; while (j n - 2 nums[j - 1] nums[j]) j; } i; while (i n - 3 nums[i - 1] nums[i]) i; } return result; } };