LeetCode数组高频题解析：双指针技巧实战指南（C++版）
LeetCode数组高频题解析：双指针技巧实战指南（C++版）
在算法面试和竞赛中，数组类题目往往是最基础也最常考的类型。而双指针技巧，则是解决这类问题的利器之一。本文将深入剖析双指针在LeetCode数组题中的应用，通过典型例题的C++实现，帮助开发者掌握这一核心技巧。
1. 双指针技巧概述
双指针是一种通过维护两个指针来高效解决问题的算法思想。在处理数组问题时，它能将原本O(n²)的时间复杂度优化到O(n)，极大提升算法效率。根据指针移动方向的不同，双指针主要分为以下两种类型：
- 同向指针（快慢指针）：两个指针从同一侧出发，以不同速度移动
- 相向指针（左右指针）：两个指针分别从数组两端出发，向中间移动
// 快慢指针基本框架 int slow = 0; for (int fast = 0; fast < nums.size(); fast++) { if (condition) { nums[slow++] = nums[fast]; } } // 左右指针基本框架 int left = 0, right = nums.size() - 1; while (left < right) { if (condition1) left++; else if (condition2) right--; }2. 快慢指针实战应用
2.1 原地修改数组
快慢指针最典型的应用场景就是原地修改数组，这类问题通常要求在不使用额外空间的情况下修改数组。
例题：移除元素（LeetCode 27）
class Solution { public: int removeElement(vector<int>& nums, int val) { int slow = 0; for (int fast = 0; fast < nums.size(); fast++) { if (nums[fast] != val) { nums[slow++] = nums[fast]; } } return slow; } };关键点分析：
- 慢指针
slow指向下一个有效元素的位置 - 快指针
fast遍历整个数组 - 时间复杂度O(n)，空间复杂度O(1)
变式：删除排序数组中的重复项（LeetCode 26）
class Solution { public: 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 链表中的快慢指针
虽然本文聚焦数组，但快慢指针在链表问题中同样适用：
// 链表去重示例 ListNode* deleteDuplicates(ListNode* head) { if (!head) return nullptr; ListNode *slow = head, *fast = head; while (fast) { if (slow->val != fast->val) { slow->next = fast; slow = slow->next; } fast = fast->next; } slow->next = nullptr; return head; }3. 左右指针高级应用
3.1 滑动窗口技巧
滑动窗口是左右指针的一种特殊形式，常用于解决子数组/子串问题。
例题：长度最小的子数组（LeetCode 209）
class Solution { public: int minSubArrayLen(int target, vector<int>& nums) { int left = 0, sum = 0; int min_len = INT_MAX; for (int right = 0; right < nums.size(); right++) { sum += nums[right]; while (sum >= target) { min_len = min(min_len, right - left + 1); sum -= nums[left++]; } } return min_len == INT_MAX ? 0 : min_len; } };性能对比：
| 方法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 暴力法 | O(n²) | O(1) | 小规模数据 |
| 滑动窗口 | O(n) | O(1) | 大规模数据 |
3.2 有序数组的双指针
对于已排序数组，双指针可以高效解决许多问题。
例题：有序数组的平方（LeetCode 977）
class Solution { public: vector<int> sortedSquares(vector<int>& nums) { int left = 0, right = nums.size() - 1; vector<int> res(nums.size()); int pos = nums.size() - 1; while (left <= right) { if (abs(nums[left]) > abs(nums[right])) { res[pos--] = nums[left] * nums[left]; left++; } else { res[pos--] = nums[right] * nums[right]; right--; } } return res; } };4. 双指针综合应用
4.1 螺旋矩阵问题
虽然螺旋矩阵(LeetCode 59)不直接使用双指针，但边界收缩的思想与双指针异曲同工：
class Solution { public: vector<vector<int>> generateMatrix(int n) { vector<vector<int>> matrix(n, vector<int>(n)); int num = 1; int top = 0, bottom = n-1, left = 0, right = n-1; while (num <= n*n) { for (int i = left; i <= right; i++) matrix[top][i] = num++; top++; for (int i = top; i <= bottom; i++) matrix[i][right] = num++; right--; for (int i = right; i >= left; i--) matrix[bottom][i] = num++; bottom--; for (int i = bottom; i >= top; i--) matrix[i][left] = num++; left++; } return matrix; } };4.2 复杂滑动窗口问题
例题：最小覆盖子串（LeetCode 76）
class Solution { public: string minWindow(string s, string t) { unordered_map<char, int> need, window; for (char c : t) need[c]++; int left = 0, right = 0; int valid = 0; int start = 0, len = INT_MAX; while (right < s.size()) { char c = s[right++]; if (need.count(c)) { window[c]++; if (window[c] == need[c]) valid++; } while (valid == need.size()) { if (right - left < len) { start = left; len = right - left; } char d = s[left++]; if (need.count(d)) { if (window[d] == need[d]) valid--; window[d]--; } } } return len == INT_MAX ? "" : s.substr(start, len); } };优化技巧：
- 使用哈希表记录字符需求
valid计数器避免频繁遍历检查- 收缩窗口时更新最小长度
5. 双指针的边界条件处理
在实际编码中，双指针算法的边界条件需要特别注意：
- 指针移动时机：确保在正确条件下移动指针
- 循环终止条件：
while(left <= right)与while(left < right)的区别 - 空输入处理：总是先检查输入是否为空
- 重复元素处理：在有重复元素时需要额外判断
// 二分查找中的边界处理示例 int binarySearch(vector<int>& nums, int target) { int left = 0, right = nums.size() - 1; while (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; } return -1; }掌握双指针技巧后，可以解决LeetCode上大量数组相关问题。在实际面试中，建议先从暴力解法入手，再分析如何用双指针优化，最后讨论时间复杂度和边界条件。