1. 顺序表OJ题的双指针解法精要顺序表作为线性表最基础的存储结构在算法面试中出现的频率高达73%根据LeetCode2022年度报告。双指针法之所以被称为超级实用是因为它能将许多O(n²)暴力解法优化到O(n)级别。我们先看一个典型案例删除有序顺序表中的重复元素。传统做法需要嵌套循环遍历时间复杂度O(n²)void removeDuplicates(int* nums, int numsSize) { for (int i 0; i numsSize; i) { for (int j i 1; j numsSize; j) { if (nums[i] nums[j]) { // 移动后续元素... } } } }而双指针解法仅需单次遍历int removeDuplicates(int* nums, int numsSize) { if (numsSize 0) return 0; int slow 0; for (int fast 1; fast numsSize; fast) { if (nums[fast] ! nums[slow]) { slow; nums[slow] nums[fast]; } } return slow 1; }这里slow指针标记唯一元素的位置fast指针探索新元素。当发现不重复元素时slow前进并接收新值。这种模式在80%的顺序表去重问题中都可套用。关键理解双指针法的本质是通过指针的相对运动将原本需要多次遍历的信息在一次遍历中完成比对和处理。slow代表已处理区域的边界fast代表待探索区域的先锋。2. 双指针法的三大经典应用场景2.1 快慢指针检测循环判断顺序表是否存在循环引用时设置不同步长的双指针bool hasCycle(int* nums, int numsSize) { int slow 0, fast 0; do { slow nums[slow]; fast nums[nums[fast]]; } while (slow ! fast fast numsSize); return slow fast fast numsSize; }fast指针每次移动两步slow移动一步。如果有环fast必定会追上slow。这个技巧在链表环检测中同样适用。2.2 左右指针逼近目标在有序顺序表中寻找两数之和int* twoSum(int* nums, int numsSize, int target) { int left 0, right numsSize - 1; while (left right) { int sum nums[left] nums[right]; if (sum target) { return (int[]){left, right}; } else if (sum target) { left; } else { right--; } } return NULL; }左右指针从两端向中间逼近根据当前和与目标值的比较决定移动哪个指针。时间复杂度从暴力法的O(n²)降至O(n)。2.3 滑动窗口统计子串统计顺序表中满足条件的连续子序列int countSubarrays(int* nums, int numsSize, int k) { int left 0, count 0, sum 0; for (int right 0; right numsSize; right) { sum nums[right]; while (sum k) { sum - nums[left]; } count right - left 1; } return count; }窗口右边界拓展直到不满足条件然后左边界收缩。这种动态维护窗口的技巧在字符串匹配中也十分常见。3. 双指针法的边界处理艺术3.1 指针越界防护在移动fast指针时必须确保不会越界// 错误示范 while (nums[fast] ! target) { fast 2; // 可能越界 } // 正确做法 while (fast numsSize nums[fast] ! target) { fast 2; }3.2 空表与单元素处理很多OJ题的测试用例包含边界情况// 在反转顺序表时 if (numsSize 0 || numsSize 1) { return; // 直接返回 }3.3 指针重合时的特殊处理当双指针重合时可能需要特殊逻辑while (left right) { if (left right) { // 处理中间唯一元素 break; } // 正常处理 }4. 双指针实战接雨水问题LeetCode 42题接雨水是双指针法的经典考题。我们通过它展示完整的解题思路4.1 问题分析给定表示高度的顺序表计算能接多少雨水。关键点在于每个位置的水位由左右两侧最高柱子的较小值决定。4.2 双指针解法int trap(int* height, int heightSize) { int left 0, right heightSize - 1; int left_max 0, right_max 0; int result 0; while (left right) { if (height[left] height[right]) { if (height[left] left_max) { left_max height[left]; } else { result left_max - height[left]; } left; } else { if (height[right] right_max) { right_max height[right]; } else { result right_max - height[right]; } right--; } } return result; }4.3 复杂度分析时间复杂度O(n)单次遍历空间复杂度O(1)仅使用常数空间这个解法巧妙之处在于每次移动较矮一侧的指针确保另一侧总有更高的柱子形成边界。我在华为OD机试中遇到过该问题的变种当时没有理解这个核心思想导致超时。5. 双指针法的调试技巧5.1 可视化打印在调试时打印指针位置和关键变量printf(slow%d, fast%d, nums[slow]%d, nums[fast]%d\n, slow, fast, nums[slow], nums[fast]);5.2 边界测试用例设计针对双指针法必须测试空顺序表单元素顺序表全相同元素已排序和逆序情况包含重复元素的特殊情况5.3 内存访问检查使用Valgrind检测指针越界valgrind --toolmemcheck ./your_program我在处理东方博宜OJ 1101题时就因为未检查指针越界导致段错误。后来养成了在每次指针移动前添加边界检查的习惯。6. 双指针与其他算法的组合应用6.1 双指针二分查找在旋转排序数组中搜索int search(int* nums, int numsSize, int target) { int left 0, right numsSize - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) return mid; if (nums[left] nums[mid]) { if (nums[left] target target nums[mid]) { right mid - 1; } else { left mid 1; } } else { if (nums[mid] target target nums[right]) { left mid 1; } else { right mid - 1; } } } return -1; }6.2 双指针哈希表解决两数之和问题int* twoSum(int* nums, int numsSize, int target) { // 先排序再用双指针 qsort(nums, numsSize, sizeof(int), compare); int left 0, right numsSize - 1; while (left right) { int sum nums[left] nums[right]; if (sum target) { return (int[]){left, right}; } else if (sum target) { left; } else { right--; } } return NULL; }6.3 多指针协同如荷兰国旗问题使用三指针分区void sortColors(int* nums, int numsSize) { int low 0, mid 0, high numsSize - 1; while (mid high) { if (nums[mid] 0) { swap(nums[low], nums[mid]); } else if (nums[mid] 1) { mid; } else { swap(nums[mid], nums[high--]); } } }7. 双指针法的常见误区与优化7.1 指针移动条件错误在移除元素时容易错误移动指针// 错误示范 while (fast numsSize) { if (nums[fast] ! val) { nums[slow] nums[fast]; fast; // 应该slow也移动 } } // 正确版本 while (fast numsSize) { if (nums[fast] ! val) { nums[slow] nums[fast]; } fast; }7.2 未利用有序性对于已排序顺序表可以提前终止循环// 在两数之和问题中 while (left right) { int sum nums[left] nums[right]; if (sum target) { return ...; } else if (sum target) { left; } else { right--; } // 可以添加提前终止条件 if (nums[left] target) break; }7.3 内存重叠处理当源和目标内存重叠时memcpy可能出错// 安全做法 void removeElement(int* nums, int numsSize, int val) { int slow 0; for (int fast 0; fast numsSize; fast) { if (nums[fast] ! val) { if (slow ! fast) { // 避免自我赋值 nums[slow] nums[fast]; } slow; } } }我在做中南大学C语言试卷时就曾因为忽略内存重叠导致数据错误。后来在华为安全编程规范中学到对于可能重叠的内存操作必须添加位置判断。