算法工具箱之双指针

双指针是算法中一种常用的技巧特别适用于​​数组​​和​​链表​​类问题。它的核心思想是使用两个指针以不同的策略遍历数据结构从而高效地解决问题。双指针常见的三种类型1快慢指针两个指针从同一侧开始移动但移动速度不同。适用范围这种⽅法对于处理环形链表或数组⾮常有⽤。实现方式快慢指针的实现方式有多种但常见的是在⼀次循环中每次让慢的指针向后移动⼀位⽽快的指针往后移动两位实现⼀快⼀慢。下面的例题会解析快慢指针的用法核心思想这个代码中我们会用到两个指针一个fast指针一个slow指针快指针用来遍历整个数组而慢指针用来指向非0的位置遇到非0元素1即可class Solution { public: void moveZeroes(vectorint nums) { int slow -1; int fast 0; for(;fast nums.size();fast) { if(nums[fast]) { swap(nums[slow],nums[fast]); } } } };2左右指针对撞指针两个指针分别指向序列的​​开头左和结尾右​​然后向中间移动直到它们相遇。特点​​指针移动方向是​​相对的​​。适用范围主要适用于​​数组​​和​​字符串​​通常要求序列是​​有序的​​。来一道例题来解析对撞指针的用法class Solution { public: int maxArea(vectorint height) { int left 0; int right height.size() - 1; int ret 0; while(left right) { int high min(height[right],height[left]); int width right - left; int nowret high * width; ret max(ret,nowret); if(height[right] height[left]) { left; } else { right--; } } return ret; } };这道题让我们求承最多水的容器也就是求面积最大的区域所以这道题我们应该找出面积最大的区域。我们可以先定义出一个left和一个right用来表示height数组中的最左侧位置和最右侧位置然后我们通过min来比较谁的高度比较小并且与距离相乘用来求出当前区域的面积。然后与最大的面积相比留下最大的面积随后我们比较right和left所对应的数组元素的高度较小的一方缩进数组随后再重复以上方法进而比较出面积最大的区域。为什么要移去较小边界的那一端呢因为当我们移动较高边界那一端时最低的高度不变反而宽度减小这样并不会生成面积更大的数组反而当我们把数组较小的那一端移去虽然宽度减小但是有可能高度会增加进而产生的面积可能比原来的最大面积更大。3滑动窗口滑动窗口是双指针的一种高级用法两个指针形成一个窗口区间通过移动左右指针来动态地维护这个窗口从而解决问题。适用场景寻找满足某种条件的连续子数组或子字符串如最小覆盖子串、长度最小的子数组、无重复字符的最长子串。。核心思想1.right指针向右扩张窗口直到窗口内的元素满足条件。2.然后left指针向右收缩窗口同时更新最优解直到窗口不再满足条件。3.重复步骤 1 和 2直到right到达末尾。例题class Solution { public: int minSubArrayLen(int target, vectorint nums) { int left 0; int right 0; int sum 0; int min_len INT_MAX; for(;right nums.size();right) { sum nums[right]; while(sum target) { min_len min(min_len,right - left 1); sum - nums[left]; left; } } return (min_len INT_MAX ? 0 : min_len); } };我们定义两个指针left和right初始都指向数组的起始位置。再定义出定义sum记录当前窗口的和min_len记录最小长度。随后将nums[right]加到sum中表示扩展窗口的右边界。right向右移动直到sum target。当sum target时尝试收缩窗口的左边界计算当前窗口的长度right - left 1并更新min_len。将nums[left]从sum中减去然后left右移。重复此过程直到sum target窗口不再满足条件。当right遍历完整个数组后返回min_len。如果min_len未被更新即没有满足条件的子数组返回0。为什么滑动窗口有效并且时间复杂度更低呢因为这个数组都是正整数这意味着我们向右扩展窗口时数组内元素之和是严格递增的当我们向右收缩窗口时数组内元素之和也是严格递减的。不会出现反复回溯的情况。通过left和right两个指针滑动窗口可以不遗漏任何可能的连续的子数组。避免了暴力解法中的重复计算。通过每次发现sum target,记录当前窗口的长度并且进行比较一旦sum target就停止收缩直接扩展窗口避免无效计算。时间复杂度虽然代码是两层循环但是我们的 left 指针和 最多都往后移动 n 次。因此时间复杂度是 O(N) 。