雙指針法

• 前言
• 167.兩數之和 II - 輸入有序數組
• 88.合并兩個有序數組
• 142. 環形鏈表 II
• 633.平方數之和
• 680. 驗證回文字符串 Ⅱ
• 27. 移除元素
• 344. 反轉字符串
• 劍指 Offer 05. 替換空格
• 151. 翻轉字符串里的單詞
• 206.反轉鏈表
• 125. 驗證回文串
• 19. 刪除鏈表的倒數第 N 個結點
• 面試題 02.02. 返回倒數第 k 個節點

前言

雙指針主要用于遍歷數組，兩個指針指向不同的元素，從而協同完成任務。也可以延伸到多個數組的多個指針。

若兩個指針指向同一數組，遍歷方向相同且不會相交，則也稱為滑動窗口（兩個指針包圍的區域即為當前的窗口），經常用于區間搜索。

若兩個指針指向同一數組，但是遍歷方向相反，則可以用來進行搜索，待搜索的數組往往是排好序的。

167.兩數之和 II - 輸入有序數組

題解

這道題還是比較簡單的，因為數組已經排好序了，所以我們很容易就想到一個方法：

我們可以使用兩個指針$s,l$，其中$s$指向最小值，$l$指向最大值。當兩指針的和小于目標值時，$s$指針向右移動，當兩指針的和大于目標值時，$l$指針向左移動，這樣一定可以得到最優解，就是這樣。

代碼

//過于簡單，我就不寫注釋了。 vector<int> twoSum(vector<int>& numbers, int target) {int l = 0, r = numbers.size() - 1, sum;while (l < r) {sum = numbers[l] + numbers[r];if (sum == target) break;if (sum < target) ++l;else --r;}return vector<int>{l + 1, r + 1}; }

88.合并兩個有序數組

題解
因為這兩個數組已經排好序，我們可以把兩個指針分別放在兩個數組的末尾，即 nums1 的 m m 1 位和 nums2 的 n n 1 位。每次將較大的那個數字復制到 nums1 的后邊，然后向前移動一位。
因為我們也要定位 nums1 的末尾，所以我們還需要第三個指針，以便復制。
在以下的代碼里，我們直接利用 m 和 n 當作兩個數組的指針，再額外創立一個 $p$ 指針，起
始位置為 $m+n,n1$。每次向前移動 $m$ 或 $n$ 的時候，也要向前移動 $p$。這里需要注意，如果 $num$
的數字已經復制完，不要忘記把 nums2 的數字繼續復制；如果 nums2 的數字已經復制完，剩余
nums1 的數字不需要改變，因為它們已經被排好序。

這道題用圖更好理解，所以推薦查看：leetcode官方解題

注意： a++ 和 ++a都是a+1,但是a++ 返回a，然后再將a+1；
++a返回a+1。

代碼

class Solution { public:void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {int p = m-- + n-- -1; //這里廚初始化p = m + n -1,就指向nums1的最后一位，然后n--，m--。while(m>=0 && n>=0){nums1[p--] = nums1[m] > nums2[n] ? nums1[m--] : nums2[n--];//三目運算符 }while(n >= 0){nums1[p--] = nums2[n--]; }} };

142. 環形鏈表 II

題解
這道題可以使用快慢指針解決，快指針$fast$，慢指針$slow$，快指針每次走兩步，滿指針每次走一步，如果鏈表中存在環路，那么快指針和慢指針一定會相遇。
當 slow 和 fast 第一次相遇時，我們將 fast 重新移動到鏈表開頭，并讓 slow 和 fast 每次都前進一步。當 slow 和 fast 第二次相遇時，相遇的節點即為環路的開始點。

代碼

class Solution { public:ListNode *detectCycle(ListNode *head) {if (head == NULL || head->next == NULL)//這種情況下一定沒環{return NULL;}ListNode* fast=head;ListNode* slow=head;//初始哈快慢指針while (fast->next !=NULL && fast->next->next != NULL)//確保環存在{fast=fast->next->next;//快指針一次走兩步slow=slow->next;//慢指針一次走一步。if (fast==slow)//如果快慢指針相遇{slow=head;//慢指針移到鏈表頭while (slow != fast){slow=slow->next;fast=fast->next;}//指針再次相遇即為環路開始點。return slow;}}return NULL;//如果不存在環路，返回NULL。} };

633.平方數之和

題解
因為$C$為兩個數的平方值和，所以這兩個數都小于$sqrt(C)$，我們初始化兩個指針，一個初始化為0，另一個初始化為$sqrt(C)+1$，因為$sqrt()$向下取整，所以要加1。如果兩數平方值的和大于$C$，右指針向左移動；如果小于，左指針向右移。

代碼

class Solution { public:bool judgeSquareSum(int c) {unsigned int left =0,right = sqrt(c)+1;//初始化左右指針unsigned int powSum;//兩數平方的和while(right>=left){powSum = left*left+right*right;if(powSum==c) return true;else if(powSum>c) --right;else if(powSum<c) ++left;}return false;} };

680. 驗證回文字符串 Ⅱ

題解

代碼

//太簡單，不寫注釋 class Solution { public:bool checkPalindrome(const string& s, int low, int high) {for (int i = low, j = high; i < j; ++i, --j) {if (s[i] != s[j]) {return false;}}return true;}bool validPalindrome(string s) {int low = 0, high = s.size() - 1;while (low < high) {char c1 = s[low], c2 = s[high];if (c1 == c2) {++low;--high;} else {return checkPalindrome(s, low, high - 1) || checkPalindrome(s, low + 1, high);}}return true;} };

27. 移除元素

題解

先來個暴力解法：

class Solution { public:int removeElement(vector<int>& nums, int val) {int size =nums.size();for(int i =0;i <size;++i){if(nums[i]==val){for(int j = i+1;j<size;++j){nums[j-1] =nums[j];}--i;--size;}}return size;} };

暴力解法是可以通過的，但是你能滿足嗎？你不能滿足！！！
下面是雙指針法：

代碼

class Solution { public:int removeElement(vector<int>& nums, int val) {int slowIndex = 0;for(int fastIndex =0;fastIndex<nums.size();++fastIndex){if(val != nums[fastIndex])//如果快指針指向val的值，慢指針就會停止，直到快指針指向不同的值。{nums[slowIndex++] = nums[fastIndex];}}return slowIndex;} };

344. 反轉字符串

題解

其實這道題可以直接用C++的庫函數解決，但這樣沒有什么意義。

我們定義兩個指針（也可以說是索引下表），一個從字符串前面，一個從字符串后面，兩個指針同時向中間移動，并交換元素。

代碼

class Solution { public:void swap(char& i,char &j){//這是一種不常見的交換元素方式，根據^（異或）的性質：a ^ a = 0。（參見《深入理解計算機系統》）i ^= j;j ^= i;i ^= j;}void reverseString(vector<char>& s) {for(int i =0,j=s.size()-1;i<s.size()/2;++i,--j){swap(s[i],s[j]);} } };

劍指 Offer 05. 替換空格

題解
如果想把這道題目做到極致，就不要只用額外的輔助空間了！

首先擴充數組到每個空格替換成 “%20” 之后的大小。

然后從后向前替換空格，也就是雙指針法，過程如下：

$i$指向新長度的末尾，$j$指向舊長度的末尾。
代碼

class Solution { public:string replaceSpace(string s) {int count = 0; // 統計空格的個數int sOldSize = s.size();for (int i = 0; i < s.size(); i++) {if (s[i] == ' ') {count++;}}// 擴充字符串s的大小，也就是每個空格替換成"%20"之后的大小s.resize(s.size() + count * 2);int sNewSize = s.size();// 從后先前將空格替換為"%20"for (int i = sNewSize - 1, j = sOldSize - 1; j < i; i--, j--) {if (s[j] != ' ') {s[i] = s[j];} else {s[i] = '0';s[i - 1] = '2';s[i - 2] = '%';i -= 2;}}return s;} };

151. 翻轉字符串里的單詞

206.反轉鏈表

代碼

class Solution { public:ListNode* reverseList(ListNode* head) {ListNode* temp; // 保存cur的下一個節點ListNode* cur = head;ListNode* pre = NULL;while(cur) {temp = cur->next; // 保存一下 cur的下一個節點，因為接下來要改變cur->nextcur->next = pre; // 翻轉操作// 更新pre 和 cur指針pre = cur;cur = temp;}return pre;} };

125. 驗證回文串

代碼

class Solution { public:bool isPalindrome(string s) {string str;for(auto i : s){if(isalnum(i))//先除了字母和數字之外的其他字符//isalnum()函數用來判斷是否是字母或者是數字{str +=tolower(i);}}for(int i = 0,j =str.size()-1; i<j; ++i,--j)//通過前后兩個指針，判斷是否對稱。{if(str[i] != str[j]){return false;}}return true;} };

19. 刪除鏈表的倒數第 N 個結點

代碼

/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/ class Solution { public:ListNode* removeNthFromEnd(ListNode* head, int n) {if(!head->next) return nullptr;//如果鏈表就一個元素，那也只能去掉一個，所以就返回nullptr。ListNode* fast = head;ListNode* slow = head;//初始化快指針//快指針先走n步，然后慢指針在和快指針同步走，這樣的話，當快指針走到鏈表結尾時，慢指針剛好到達我們要去掉的元素之前的一個元素//這樣slow->next =slow -> next ->next就可以從鏈表中去掉要除去的元素了。for(int i =0; i<n;--n){fast=fast->next;if(!fast)//如果快指針為nullptr說明點前題目要去除的元素為第一個元素，那么，直接返回鏈表的第二個元素就可以了。{return head->next;}}while(fast->next){slow = slow->next;fast = fast->next;}slow->next =slow->next->next;return head;} };

面試題 02.02. 返回倒數第 k 個節點

題解
這種題的雙指針解法大同小異，沒有什么新意…
代碼

* Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/ class Solution { public:int kthToLast(ListNode* head, int k) {ListNode* fast =head;ListNode* slow =head;for(int i =0;i<k;--k){fast =fast->next;if(!fast){return head -> val;}}while(fast){fast =fast->next;if(!fast){return slow->next->val;}slow =slow->next;}return -1;//這塊有一點不完美//因為程序不可能運行到這，所以返回啥都可以。} };

持續更新中…

總結

以上是生活随笔為你收集整理的双指针法（leetcode分类解题，C++代码详细注释）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。