雙指針技巧在C++中的應用：從基礎到進階

1.簡介

2.同向雙指針

2.1.數組去重

2.2.最大子數組和

2.3.鏈表反轉

2.4.字符串匹配（簡單版）

3.對向雙指針

3.1.兩數之和（有序數組）

3.2.盛最多水的容器

4.快慢指針

4.1.判斷鏈表是否有環

4.2.尋找鏈表的中間節點

4.3.合并兩個有序鏈表

5.總結

1.簡介

????????雙指針技巧是一種常見的算法技巧，廣泛應用于排序、查找、求和等問題中，尤其在處理數組、鏈表等數據結構時，表現出顯著的優勢。通過合理地使用兩個指針來解決問題，可以減少時間復雜度，提升算法效率。

????????雙指針技巧在 C++ 中應用廣泛，能高效解決諸多算法問題，主要分為同向雙指針、對向雙指針和快慢雙指針這幾類。

????????以下結合具體應用案例來介紹。

2.同向雙指針

2.1.數組去重

????????給定一個有序數組，要求去除重復元素并返回新數組的長度。以[1, 1, 2, 2, 3, 4]為例，借助同向雙指針，慢指針slow用于記錄不重復元素的存儲位置，快指針fast遍歷數組。當fast指向的元素與slow指向的元素不同時，將fast指向的元素賦值給slow + 1的位置，然后slow后移。

? ? ? ? 代碼如下：

int removeDuplicates(vector<int>& nums) {if (nums.empty()) return 0;int slow = 0;for (int fast = 1; fast < nums.size(); ++fast) {if (nums[fast] != nums[slow]) {nums[++slow] = nums[fast];}}return slow + 1;
}

2.2.最大子數組和

給定一個整數數組，找出具有最大和的連續子數組（子數組至少包含一個元素）。

思路：

使用一個指針來表示當前的窗口區間。
每次擴展窗口，計算窗口內的元素和，并更新最大和。
一旦當前窗口的和小于0，可以通過左指針縮小窗口，減少不必要的計算。

#include <iostream>
#include <vector>
usingnamespacestd;int maxSubArray(const vector<int>& nums) {int max_sum = nums[0], current_sum = nums[0];for (int i = 1; i < nums.size(); i++) {current_sum = max(nums[i], current_sum + nums[i]);max_sum = max(max_sum, current_sum);}return max_sum;
}int main() {vector<int> nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};cout << "Maximum Subarray Sum: " << maxSubArray(nums) << endl;return 0;
}

2.3.鏈表反轉

反轉鏈表的經典問題，可以通過雙指針技巧進行高效處理。

思路：

使用兩個指針，一個指向當前節點，另一個指向前一個節點。
每次將當前節點的指針指向前一個節點，逐步反轉鏈表。

#include <iostream>
usingnamespacestd;struct ListNode {int val;ListNode* next;ListNode(int x) : val(x), next(nullptr) {}
};ListNode* reverseList(ListNode* head) {ListNode* prev = nullptr;ListNode* current = head;while (current != nullptr) {ListNode* nextNode = current->next;current->next = prev;prev = current;current = nextNode;}return prev;
}void printList(ListNode* head) {ListNode* temp = head;while (temp != nullptr) {cout << temp->val << " ";temp = temp->next;}cout << endl;
}int main() {ListNode* head = new ListNode(1);head->next = new ListNode(2);head->next->next = new ListNode(3);head->next->next->next = new ListNode(4);cout << "Original List: ";printList(head);ListNode* reversed = reverseList(head);cout << "Reversed List: ";printList(reversed);return 0;
}

2.4.字符串匹配（簡單版）

????????在一個長字符串中查找短字符串首次出現的位置（簡單的暴力匹配改進）。比如在字符串"ABABDABACDABABCABAB"中找"ABABC"。長字符串指針i和短字符串指針j同向移動，當j指向的字符與i指向的字符匹配時，i和j都后移；若不匹配，i回退到上次匹配起始位置的下一個位置，j歸零重新匹配。

? ? ? ? 具體代碼如下：

int strStr(string haystack, string needle) {int m = haystack.size(), n = needle.size();for (int i = 0; i <= m - n; ++i) {int j = 0;for (; j < n; ++j) {if (haystack[i + j] != needle[j]) {break;}}if (j == n) {return i;}}return -1;
}

3.對向雙指針

3.1.兩數之和（有序數組）

假設有一個排序好的數組，我們需要在該數組中找到兩個數，使得它們的和等于目標值。

思路：

定義兩個指針，分別指向數組的開頭和結尾。
根據當前兩指針指向的數值之和與目標值的關系，決定移動哪個指針。
如果兩數之和大于目標值，則移動右指針，減小和；如果小于目標值，則移動左指針，增大和。

? ? ? ? 具體代碼如下：

#include <iostream>
#include <vector>
usingnamespacestd;bool twoSum(const vector<int>& nums, int target) {int left = 0, right = nums.size() - 1;while (left < right) {int sum = nums[left] + nums[right];if (sum == target) {return true;} elseif (sum < target) {left++;} else {right--;}}return false;
}int main() {vector<int> nums = {1, 2, 3, 4, 6};int target = 10;cout << (twoSum(nums, target) ? "Found" : "Not found") << endl;return 0;
}

3.2.盛最多水的容器

????????給定一個數組，數組中的每個元素表示一個垂直的線段高度，線段之間的距離是相鄰元素的索引差，要求找出兩條線段，使得它們與 x 軸構成的容器能容納最多的水。以[1, 8, 6, 2, 5, 4, 8, 3, 7]為例，使用對向雙指針，指針left和right分別指向數組兩端。計算當前容器的面積area = min(height[left], height[right]) * (right - left)，更新最大面積。然后比較height[left]和height[right]，較小值對應的指針向內移動，重復計算面積和移動指針的操作。

? ? ? ? 具體代碼如下：

int maxArea(vector<int>& height) {int left = 0, right = height.size() - 1;int maxArea = 0;while (left < right) {int area = min(height[left], height[right]) * (right - left);maxArea = max(maxArea, area);if (height[left] < height[right]) {left++;} else {right--;}}return maxArea;
}

4.快慢指針

????????快慢指針的基本思路是：用兩個指針（通常稱為快指針和慢指針）遍歷數據結構。慢指針每次移動一步，而快指針每次移動兩步。由于快指針移動的速度較快，它可以在一些特定場景下幫助我們高效地解決問題。

4.1.判斷鏈表是否有環

????????環形鏈表是一個常見的數據結構問題，要求檢測鏈表中是否存在環。使用快慢指針的算法非常高效。基本思路是：讓快指針每次走兩步，慢指針每次走一步。如果鏈表中存在環，快慢指針最終會相遇；如果鏈表沒有環，快指針會先到達鏈表的尾部。

? ? ? ? 具體實現代碼如下：

#include <iostream>struct ListNode {int val;ListNode* next;ListNode(int x) : val(x), next(nullptr) {}
};bool hasCycle(ListNode* head) {if (!head || !head->next) returnfalse;ListNode* slow = head;ListNode* fast = head;while (fast && fast->next) {slow = slow->next;           // 慢指針每次走一步fast = fast->next->next;     // 快指針每次走兩步if (slow == fast) return true; // 快慢指針相遇，說明有環}return false; // 快指針到達鏈表尾部，沒有環
}int main() {ListNode* head = new ListNode(1);head->next = new ListNode(2);head->next->next = new ListNode(3);head->next->next->next = new ListNode(4);head->next->next->next->next = head->next; // 創建環if (hasCycle(head)) {std::cout << "The linked list has a cycle." << std::endl;} else {std::cout << "The linked list does not have a cycle." << std::endl;}return0;
}

4.2.尋找鏈表的中間節點

????????另一個常見的應用是查找鏈表的中間節點。使用快慢指針時，慢指針每次走一步，快指針每次走兩步。當快指針走到鏈表末尾時，慢指針恰好到達中間節點。

????????具體實現代碼如下：

#include <iostream>struct ListNode {int val;ListNode* next;ListNode(int x) : val(x), next(nullptr) {}
};ListNode* findMiddle(ListNode* head) {if (!head) returnnullptr;ListNode* slow = head;ListNode* fast = head;while (fast && fast->next) {slow = slow->next;fast = fast->next->next;}return slow; // 慢指針指向鏈表的中間節點
}int main() {ListNode* head = new ListNode(1);head->next = new ListNode(2);head->next->next = new ListNode(3);head->next->next->next = new ListNode(4);head->next->next->next->next = new ListNode(5);ListNode* middle = findMiddle(head);if (middle) {std::cout << "The middle node value is: " << middle->val << std::endl;} else {std::cout << "The list is empty." << std::endl;}return0;
}

4.3.合并兩個有序鏈表

????????在合并兩個有序鏈表時，可以使用雙指針來實現。雖然這不是嚴格的快慢指針技巧，但它與快慢指針有一定的相似性。通過兩個指針分別遍歷兩個鏈表并比較元素，逐步合并鏈表。

????????具體實現代碼如下：

#include <iostream>struct ListNode {int val;ListNode* next;ListNode(int x) : val(x), next(nullptr) {}
};ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {ListNode dummy(0);ListNode* current = &dummy;while (l1 && l2) {if (l1->val < l2->val) {current->next = l1;l1 = l1->next;} else {current->next = l2;l2 = l2->next;}current = current->next;}if (l1) current->next = l1;if (l2) current->next = l2;return dummy.next;
}int main() {ListNode* l1 = new ListNode(1);l1->next = new ListNode(3);l1->next->next = new ListNode(5);ListNode* l2 = new ListNode(2);l2->next = new ListNode(4);l2->next->next = new ListNode(6);ListNode* mergedList = mergeTwoLists(l1, l2);while (mergedList) {std::cout << mergedList->val << " ";mergedList = mergedList->next;}std::cout << std::endl;return0;
}