算法：双指针

算法：双指针

• • 双指针
  • 快慢指针
  • 对撞指针
  • 总结

    ---

    双指针

    LeetCode 283.移动零

    以上题目要求我们把所有0移动到数组的末尾，也就是说，我们要把数组转化为以下状态：

    [ 非0区域 ] [ 0区域 ]

    像这种把一个数组划分为多个区域的题型，就是数组划分。而数组划分非常适合使用双指针算法。

    对于这道题，我们可以用两个指针，对数组进行动态的区域划分。

    其中dest指针维护一段区域，表示非0区域，cur指针与dest之间的区域是0区域。而cur后面的区域是待处理区域。

    也就是我们的数组被划分为了以下情况：

    [ 非0区域 ] [ 0区域 ] [ 待处理区域 ]

    当我们的cur移动后，对于一个新的数据，就要根据条件来决定把它放到哪一个区域去。当cur指针走到末尾，数组就被处理为了：

    [ 非0区域 ] [ 0区域 ]

    也就是题目要求的样子了。

    对于本题而言，如果新插入的数据是0，那就放到cur维护的区域里面，此时直接cur++即可；如果新插入的数据是非0，那么就放到dest的末尾，为了保证dest不会覆盖掉cur原本维护的0，因此要进行一个交换操作。

    代码如下：

    class Solution
    {public:
        void moveZeroes(vector& nums) 
        { int dest = -1;
            int cur = 0;
            int sz = nums.size();
            while (cur < sz)
            { if (nums[cur])
                    swap(nums[++dest], nums[cur]);
                cur++;
            }
        }
    };
    

    ---

    LeetCode 75.颜色分类

    这一题也是一个区域划分问题，根据上一题的思路，我们可以把数组划分为以下状态：

    [ 0区域 ] [ 1区域 ] [ 2区域 ]

    相比于上一题，这次我们要划分出三个区域来，毫无疑问就需要更多的指针来维护区域，大致可以划分为：

    [ 0区域 ] [ 1区域 ] [ 待处理 ] [ 2区域 ]

    我们让维护0区域的指针left向右拓展，维护2区域的指针right向左拓展，以及利用cur指针向右遍历数组：

    上图中，left指针左侧维护了一段0区域，left与cur之间维护了一段1区域，cur与right之间是待处理区域，right右侧是2区域。当cur往后遍历，如果遇到一个新的数据，就要决定把它放到哪一个区域去：

    1. 遇到0，就交换++left与cur的值，把0放到left后面一位，拓展left指针维护的区域
    2. 遇到1，就直接++cur，把1放到cur与left之间
    3. 遇到2，就交换--right与cur的值，把2放到right的前面一位，拓展right维护的区域

    要注意的是，当把0交给left后，cur++；但是当把2交给right后，cur不能移动。因为left后面的一位数一定是符合cur范围要求的，也就是区间(left, cur]之间的数据被交换到了cur的位置，此时不用判断被交换过来的数据。而right的前面一位数据是不确定的，也就是把区间(cur, right)之间的数据，交换给了cur。而(cur, right)之间的数据是待处理的不确定数据，因此还需要额外判断一次。比如上图中，right的前一位数据就是0，交换后状态如下：

    可以看到，cur得到的数据是0，应该被放到left维护的区域去。

    总代码如下：

    class Solution
    {public:
        void sortColors(vector& nums)
        { int left = -1;
            int right = nums.size();
            int cur = 0;
            while (cur < right)
            { if (nums[cur] == 0)
                    swap(nums[++left], nums[cur++]);
                else if (nums[cur] == 2)
                    swap(nums[--right], nums[cur]);//交换后不能cur++，进入下一轮循环在判断一次cur的值
                else
                    cur++;
            }
        }
    };
    

    ---

    快慢指针

    LeetCode 202.快乐数

    该题的意思是，每个数字的下一个数字是该数字所有位的平方和，比如 19 的下一位数字就是 1 2 + 9 2 = 82 1^{2} + 9^{2} = 82 12+92=82。一直以这个规则操作下去，会出现两种情况：

    1. 最后该数字变为1，那么该数字是快乐数
    2. 该数字陷入死循环，那么该数字不是快乐数

    • 比如19 -> 82 -> 68 -> 100 -> 1 ，最后19变成了1，所以19是一个快乐数
    • 比如2 -> 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4，可以发现其陷入了一个死循环，从4开始又以4结束，那么2就不是一个快乐数

      这题的难点不在于如何计算下一位快乐数字，而在于如何判断一个数字陷入了死循环。

      对于这种循环问题，就可以使用快慢指针。

      快慢指针规则如下：

      1. 定义两个变量fast与slow
      2. fast走2步，slow走一步
      3. 如果fast走到终点，说明没有循环
      4. 如果fast与slow相遇，说明陷入了循环

      一开始fast和slow都在起点：

      fast走两步，slow走一步：

      由于这是一个循环结构，当fast进入第二圈循环，slow还没有走完第一圈：

      这个时候，由于slow的速度为1，fast的速度为2，那么每次行动fast与slow的距离就会缩短1，最后fast一定可以遇到slow：

      此时两者相遇，说明这是一个循环结构。

      因此代码逻辑如下：

      1. 定义两个变量，fast和slow，fast走两步，slow走一步
      2. 如果fast变成1，那么该数字是快乐数，返回true
      3. 如果fast与slow相遇，那么有循环结构，该数字不是快乐数，返回false

      代码如下：

      class Solution 
      {public:
          int getNextNum(int n) //到下一个数字的函数
          
          { int num = 0;
              while (n)
              { int tmp = n % 10;
                  num += tmp * tmp;
                  n /= 10;
              }
              return num;
          }
          bool isHappy(int n) 
          { int fast = n;
              int slow = n;
              while (fast != 1)
              { fast = getNextNum(getNextNum(fast));//fast走两步
                  slow = getNextNum(slow);//slow走一步
                  if (fast == slow && fast != 1)//两者相遇，有循环
                      return false;
              } 
                  
              return true;//到这里说明fast = 1，是快乐数
          }
      };
      

      其中有一个注意点，就是条件fast == slow && fast != 1，这里一种情况就是fast虽然和slow相等，但是两者都为1，此时是快乐数。

      比如数字10，10 -> 1 -> 1，slow走第一步就是1了，fast走两步也是1，此时两者相等。

      ---

      LeetCode 141.环形链表

      本题要求判断一个链表中有没有环结构，那就是一个循环问题，要使用快慢指针。

      我们刚刚已经讲解过快慢指针了，现在我们直接说明代码逻辑：

      1. 定义两个指针fast和slow，fast走两步，slow走一步
      2. 如果fast为nullptr，说明链表无环，返回true
      3. 如果fast与slow相遇，说明有环，返回false

      代码如下：

      class Solution {public:
          bool hasCycle(ListNode* head)
          { ListNode* slow = head;
              ListNode* fast = head;
              while (fast && fast->next)
              { fast = fast->next->next;
                  slow = slow->next;
                  if (fast == slow)
                      return true;
              }
              return false;
          }
      };
      

      注意事项：

      1. 进入循环时，因为fast要走两步，因此要判断fast->next是不是空指针，否则fast->next-->next就是访问空指针行为

      ---

      LeetCode 142.环形链表II

      这道题要求我们求出环形链表的环入口，这就麻烦了，通过之前的fast与slow的快慢指针追击问题，我们已经可以判断是否存在环结构了，那么我们要如何求环入口呢？

      看到以下示意图：

      现在slow和fast刚好相遇，参数含义如下：

      L：从起点到环入口的距离

      C：环周长

      X：相遇点和环入口的距离

      由于fast的速度是slow的两倍，当slow走的距离是L + X，因此此时fast走了2(L + X)的距离。

      又由于fast一定经过了起点到入口的L距离，因此此时fast在环中走了2(L + X) - L = L + 2X的距离。

      假设fast已经在环中转了n圈，因此此时fast在环中走了nC + X的距离

      那么可以列出公式：

      n C + X = L + 2 X nC + X = L + 2X nC+X=L+2X

      变形得到：

      n C − X = L \mathbf{{\color{Red} nC - X = L} } nC−X=L

      这个公式具有重大意义，L代表起点到入口的距离，nC代表n个环周长，X代表当前相遇点与入口的距离。

      nC -X整体可以看成(n - 1)C + (C - X)，而C - X就代表相遇点开始与环入口的优弧的长度。

      此时如果让一个指针A从起点开始走L的距离所用的时间，和让一个指针B从相遇点开始走n - 1圈外加一个C - X的距离所用的时间是一致的。由于相遇点与环入口距离已经是X了，那么指针B最后刚好会走到环入口。而指针A从入口开始走L到达的地方也是环入口，因此两者相遇！

      通过这个公式可知：让一个指针从起点开始走，一个指针从相遇点开始走，两者会在环入口相遇！

      因此我们的代码逻辑如下：

      1. 定义两个指针fast和slow，fast走两步，slow走一步
      2. 如果fast为nullptr，说明链表无环，返回nullptr
      3. 如果fast与slow相遇，说明有环，开始找环入口

      • 在相遇点定义一个指针B，也就是B = slow；在起点定义一个指针A，也就是A = head
      • 两个指针各自行动，速度一致，最后A与B相遇的地方就是环入口
      • 返回A或B

      代码如下：

      class Solution
      {public:
          ListNode* detectCycle(ListNode* head)
          { ListNode* fast = head;
              ListNode* slow = head;
              while (fast && fast->next)
              { fast = fast->next->next;
                  slow = slow->next;
                  if (slow == fast)  // 有环，开始找入口
                  { ListNode* A = head;
      				ListNode* B = slow;
      				
                      while (A != B)//A与B相遇点，就是环入口
                      { A = A->next;
                          B = B->next;
                      }
                      return A;
                  }
              }
              return nullptr; //没有环，返回空指针
          }
      };
      

      ---

      ---

      对撞指针

      LCR 179.查找总价格为目标值的两个商品

      这道题给了一个升序数组，要求我们求出数组中任意两个值的和刚好为target。

      该数组有一个特点：有序数组。像这种在一个有序区间中查找两个元素，计算得到固定值的题型，就可以使用对撞指针。

      如果我们直接暴力解法的话，那就是枚举所有两两一对的元素组，直到某一对刚好和为target，时间复杂度为 O ( N 2 ) O(N^{2}) O(N2)。

      假设现在的数组为[8, 21, 27, 34, 52]，target = 61：

      因为数组具有单调性，我们可以一开始就枚举最左侧和左右侧的两个元素：

      当前8 + 52 = 60比61小，说明我们需要一个更大的值来增大当前总和。那么由于数组升序，我们只需要left++即可：

      当前21 + 52 = 73比61大，说明我们需要一个更小的值来缩小当前总和。那么由于数组升序，我们只需要right--即可：

      当前21 + 34 = 55比61小，说明我们需要一个更大的值来增大当前总和。那么由于数组升序，我们只需要left++即可：

      当前27 + 34 = 61，我们就找到了目标值，返回left与right下标即可。

      正是由于数组单调性，我们可以通过比大小来进行指针的调整，来决定当前总值要变大还是变小，如果最后left与right相遇了，说明不存在这样的和。

      为什么可以这样优化呢？看到这个例子：

      对于34而言，其要去枚举除了自己以外的所有值，但是当前21 + 34 = 55比61小，如果把21改为8，那只总和只会更小，因此我们只需要再枚举比21大的值即可。也就是通过单调性，免去了很多不必要的枚举行为。

      代码如下：

      class Solution 
      {public:
          vector twoSum(vector& price, int target)
          { int left = 0;
              int right = price.size() - 1;
              while (left < right)
              { if (price[left] + price[right] > target) //和比target大，right--
                      right--;
                  else if (price[left] + price[right] < target) //和比target小，left++
                      left++;
                  else
                      return { price[left], price[right] };
              }
              return { 0, 0 };
          }
      };
      

      ---

      LeetCode 11.盛水最多的容器

      本题要求存储的最大水量，其实也就是两个下标之间的距离right - left与min(height[left], height[right])的乘积。

      如果暴力枚举，那么就是枚举出每一对下标，然后求出最大面积，时间复杂度为 O ( N 2 ) O(N^{2}) O(N2)。

      本题也可以使用双指针的算法，水量的值与right - left与min(height[left], height[right])两个变量正相关，如果我们利用两个指针向内枚举，那么right - left这个值是一直在减小的，也就是有一项有单调性。

      对于这种，如果利用对撞指针下标向内枚举，对组成结果的某一项变量的影响是单调的，就可以考虑对撞指针。

      假设我们已经在边界上定义好了left与right指针：

      第一个问题就是，应该以什么规则进行向内移动指针？

      移动的过程中，水的宽度的一直递减的，那么我们就要尽可能找到height高的元素，来拔高水量。

      比如说当前的两个高度为3和7，由于水的高度取决于较低的那个元素，因此高度为7的指针无论怎么向内移动，水高度都不会超过3，而这个过程中宽度又是单调递减的，因此right指针向内移动，所有的结果都小于当前的水量。

      比如这个情况：

      虽然right向内移动，找到了比7更大的元素，但是由于此时水高度取决于3，而且宽度还变小了，最后总水量没有变大。

      因此每次都把比元素值较小的那个指针向内移动

      代码如下：

      class Solution
      {public:
          int maxArea(vector& height)
          { int left = 0;
              int right = height.size() - 1;
              int ret = -1;
              while (left <= right)
              { int w = right - left;//宽度
                  int h = min(height[left], height[right]);//高度
                  ret = max(ret, w * h);//更新最大水量
      			//每次都让较小的元素向内枚举
                  if (height[left] > height[right])
                      right--;
                  else
                      left++;
              }
              return ret;
          }
      };
      

      ---

      总结

      双指针

      • 数组划分使用双指针算法。

        一般处理为[A区域][B区域]...[待处理]这样的格式，当新元素符合哪一个区域特性，就放到哪一个区域中。

        快慢指针

        • 循环问题，利用快慢指针来判断是否有循环。

          相遇就是有环，如果fast走到结尾就是无环。

          如果要找循环开始节点，一个指针从头开始走，一个指针从相遇点开始走，最后会在环入口相遇。

          对撞指针

          • 在一个有序区间中查找两个元素，计算得到固定值的题型，使用对撞指针。

          • 如果利用对撞指针下标向内枚举，对组成结果的影响是单调的，就可以考虑对撞指针。

            对撞指针的特点在于利用单调性减小搜索范围。

            ---