例 1相向对撞双指针 LeetCode167 两数之和 II有序数组完整代码cpp运行vectorint twoSum(vectorint numbers, int target) { int left 0, right numbers.size() - 1; while(left right) { int sum numbers[left] numbers[right]; if(sum target) return {left1, right1}; else if(sum target) left; else right--; } return {}; }时间复杂度\(O(n)\)数组长度为 nleft只能向右、right只能向左指针永不回退两个指针合计最多移动 n 次就会相遇全程仅单层循环无嵌套所有循环内操作求和、判断、指针自增都是常数 \(O(1)\) 操作总运算次数与数组长度线性相关。 对比暴力双层循环 \(O(n^2)\)大规模数组效率差距极大。空间复杂度\(O(1)\)仅定义left、right、sum三个局部整型变量变量数量固定不随输入数组长度 n 变化原地读取原数组没有新建数组、容器等和 n 成正比的存储空间输出结果容器不计入算法额外空间复杂度。例 2同向快慢双指针 LeetCode26 删除有序数组重复项完整代码cpp运行int removeDuplicates(vectorint nums) { if(nums.empty()) return 0; int slow 0; for(int fast 1; fast nums.size(); fast) { if(nums[fast] ! nums[slow]) { slow; nums[slow] nums[fast]; } } return slow 1; }时间复杂度\(O(n)\)fast快指针从头到尾完整遍历数组循环执行次数严格等于数组长度 nslow慢指针只会单向右移最多移动 n 次循环内部判断、赋值均为常数操作仅遍历一遍数组无重复扫描。空间复杂度\(O(1)\)只开辟slow、fast两个下标变量常量空间原地覆盖修改原输入数组不额外开辟存储数组额外空间与输入规模无关。通用总结所有标准原地双指针统一结论时间复杂度\(O(n)\)空间复杂度\(O(1)\)核心保证线性时间的关键指针只能单向移动、不会折返重复扫描区间空间 \(O(1)\) 的前提原地操作不复制输入数组、不使用哈希表 / 额外数组存储数据。谢谢