双指针技巧在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;
}