《演算法:一解通全》雙指標篇——一篇解破ㄈ雙指標技巧」

前言：【雙指標】是通過兩個變數交替相向/相對移動完成任務的演算法，在陣列、鏈表相關問題上頻頻出現，下面，讓我們逐步看清雙指標

1.什么是雙指標??

不少C/C++選手初看到“雙指標”這三字常常會心生疑惑，尤其是C選手，初見時，往往會不經意聯想到二級指標，
而這里的雙指標和“指標”不是同一回事，這里的雙指標或許叫做“雙下標”、“雙索引”更適合，
雙指標是通過通過兩個變數交替相向/相對移動求解問題的演算法，具體可分為【1??左右指標，相對移動】和【2??快慢指標，同向移動】

下面具體來看這兩種雙指標的使用技巧

2.左右（對撞）指標常用技巧?

左、右指標一般用在陣列問題里面，實際上指的是兩個索引值，一般初始化為left=0,right=arr.size()-1

【1】二分搜索

下面來看最簡單的二分搜索模板👇

nt binarySearch(vector<int>& nums, int target){
  if(nums.size() == 0)
    return -1;

  int left = 0, right = nums.size() - 1;
  while(left <= right){
    // 防止(left + right) 溢位👇
    int mid = left + (right - left) / 2;
    if(nums[mid] == target){ return mid; }
    else if(nums[mid] < target) { left = mid + 1; }
    else { right = mid - 1; }
  }
  // 結束條件: left > right
  return -1;
}

【2】判斷回文串

給定一個字串，驗證它是否是回文串，只考慮字母和數字字符，可以忽略字母的大小寫，

    bool isPalindrome(string s) {
    int left=0;
    int right=s.size()-1;
    while(left<right){ //兩邊對撞
        if(s[left]!=s[right])return false;//如果不等，則直接回傳false
        left++;
        right--;
        }
    return true;
    }

例如：
第一步：最開始指標left指向的字符”c“與指標right指向的字符”c“是一樣的，

第二步：指標left向右繼續移動一位，指標right向左繼續移動一位，考察下一對字符，
同理，這時指標left指向的字符”a“與指標right指向的字符”a“是一樣的，

第三步:因此指標left向右繼續移動一位，指標right向左繼續移動一位，考察下一對字符，
這時，指標left指向的字符”t“與right指向的字符”n“是不同的，也就是說字串"catnac"不是回文串，至此，即使有剩余的字符也就不需要考慮了，

同樣：判斷回文數可以先通過to_string將其轉化為字串再進行如上判斷

【3】反轉陣列

👻一般的編程語言都會提供反轉陣列的介面（函式），不過我們還是要了解這個簡單的小輪子是怎么實作的，

void reverse(vector<int>& nums){
    int left=0;
    int right=nums.size()-1;
    while(left<right){
         //交換nums[left]和nums[right]
         int tmp=nums[left];
         nums[left]=nums[right];
         nums[right]=tmp;
         left++;
         right--;
         }
   }

以反轉字串"hello"為例

3.快慢（同步）指標常用技巧?

快慢指標一般會初始化指向鏈表的頭結點head，前進時快指標fast在前，慢指標slow在后，
快、慢指標的速度差往往相同，

【1】判斷鏈表中是否含有環

判斷單鏈表是否有環，最簡單的方法之一就是用快慢指標，
一個跑得快，一個跑得慢，如果跑得快的那個最終遇到NULL,說明鏈表不含有環；如果含有環，則快指標最終必會超慢指標一圈，并與它相遇，
猶如環形跑道上競走的跑者

代碼實作：

bool hasCycle(ListNode* head){
     ListNode* fast=head;
     ListNOde* slow=head;
     while(fast!=nullptr&&fast->next!=nullptr){
         //快指標每次跑兩步
         fast=fast->next->next;
         //慢指標每次跑一步
         slow=slow->next;
         if(fast==slow)return true;//如果存在環，則快慢指標必相遇
       }
      return false;
  }

【2】鏈表無環回傳NULL，若有環則回傳這個環的起始節點，

代碼實作：

    ListNode *detectCycle(ListNode *head) {
        ListNode* fast=head;
        ListNode* slow=head;
        while(fast!=nullptr&&fast->next!=nullptr){
            fast=fast->next->next;
            slow=slow->next;
            if(fast==slow)break;
        }//先檢驗是否有環👇
        if(fast==nullptr||fast->next==nullptr)return nullptr;
        slow=head;//先把slow指向head	
        while(slow!=fast){
            fast=fast->next;//兩指標同速前進
            slow=slow->next;
        }
        return slow;//兩個指標相遇的地方就是環開始的地方
    }

解釋：為什么兩指標第二次相遇的地方就是環開始的地方：
第一次相遇時，設快指標走了2k步，慢指標走了k步，快指標fast比慢指標正好比slow多走了k步（環的整數倍，分析易知）

設相遇點與環的起點的距離為m,則環的起點與頭結點head的距離為k-m，即：從head前進k-m步即可到達環起點
同樣，如果從相遇點繼續走k-m步，也一定到達環起點

所以，我們只要把快、慢指標中的一個重新指向head，然后兩個指標同時同速前進k-m步就會相遇，而這次的相遇點這是我們的目標

【3】尋找無環單鏈表的中間節點

ListNode* middleNode(ListNode* head) {
    ListNode* fast=head;
    ListNode* slow=head;
    while(fast!=nullptr&&fast->next!=nullptr){
        fast=fast->next->next;
        slow=slow->next;
    }
    return slow;
    }

讓快指標一次前進兩步，慢指標一次前進一步，當快指標到達鏈表盡頭時，慢指標就處于鏈表的中間位置，
若環長度為奇數，則慢指標恰在鏈表中心；
為偶數，則慢指標恰在鏈表中心偏右，

如果有需要找1/3、1/4……的節點，讓調整快、慢指標速度的倍數即可

4.總結?

1. 雙指標的最難用法是滑動視窗
   我將另做專題研究,尤其是KMP
2. 不管是【滑動視窗】還是【雙指標】，都是基于暴力解法的優化，將時間復雜度降到線性，其實都是在求解中使用一些輔助變數優化
3. 這里給出我的建議

• 多多動手畫圖，輔助分析
• 遇到BUG多多除錯，在除錯程序中仔細觀察雙指標是否按我們的想法移動

5.相關題目?

• 力扣9.回文數
• 力扣125. 驗證回文串
• 力扣344. 反轉字串
• 力扣141. 環形鏈表
• 力扣：劍指 Offer II 022. 鏈表中環的入口節點