【笔面试算法学习专栏】双指针入门：破解有序数组与原地操作的高效之道

摘要双指针算法是面试中的高频考点其核心思想是通过两个指针在数据结构上协同移动将暴力解法的O ( n 2 ) O(n^2)O(n2)时间复杂度降低到O ( n ) O(n)O(n)。本文将通过三道经典题目——两数之和II167、移动零283和反转字符串344——系统讲解双指针的基础模式与实现技巧帮助读者建立对双指针思想的直观理解为进阶题目打下坚实基础。一、为什么需要双指针在算法学习中我们经常遇到这样的问题给定一个数组需要找出满足某种条件的元素对。暴力解法往往是双重循环时间复杂度为O ( n 2 ) O(n^2)O(n2)。以两数之和为例如果数组中有10 5 10^5105个元素暴力解法需要进行10 10 10^{10}1010次比较这在实际应用中是不可接受的。双指针技巧的出现就是为了解决这类问题。其核心思想是利用数组或链表的有序性通过两个指针从不同位置出发根据比较结果动态调整指针移动方向从而将时间复杂度从O ( n 2 ) O(n^2)O(n2)降低到O ( n ) O(n)O(n)。双指针之所以高效关键在于它避免了无效比较。在暴力解法中我们可能会反复比较已经确定不可能的元素对而双指针通过有序移动确保每次比较都是有意义的。二、双指针的三种基础模式在深入具体题目之前我们需要理解双指针的三种基础模式2.1 对撞指针Two Pointers / Opposite Pointers两个指针分别位于数组的两端向中间移动。这种模式适用于有序数组常用于查找满足某种条件的元素对。[left] [right] ↓ ↓ [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]2.2 快慢指针Fast and Slow Pointers两个指针从同一端出发移动速度不同。快指针用于遍历慢指针用于标记需要保留的位置。这种模式常用于原地操作类问题。[slow] [fast] ↓ ↓ [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]2.3 滑动窗口Sliding Window两个指针维护一个窗口窗口大小可以动态调整。虽然严格来说滑动窗口是双指针的扩展但它在处理子数组问题时非常有用。下面我们通过三道经典题目深入理解这些模式。三、LeetCode 167两数之和 II - 输入有序数组3.1 题目分析给你一个下标从 1 开始的整数数组 numbers该数组已按非递减顺序排列请你从数组中找出两项之和等于目标值 target 的数并返回它们的下标。返回的下标值下标从 1 开始应符合numbers[index1] numbers[index2] target。关键信息数组已按非递减顺序排列可能包含重复元素返回的下标从1开始不是从0开始假设每个输入恰好只有一个解决方案不能重复使用同一个元素3.2 暴力解法分析如果采用暴力的双重循环deftwoSum(numbers,target):nlen(numbers)foriinrange(n):forjinrange(i1,n):ifnumbers[i]numbers[j]target:return[i1,j1]# 注意下标1时间复杂度O ( n 2 ) O(n^2)O(n2)空间复杂度O ( 1 ) O(1)O(1)这显然不够优雅。我们需要利用数组有序这个关键信息。3.3 对撞指针解法由于数组有序如果两个指针分别指向首尾如果numbers[left] numbers[right] target说明右侧值太大需要减小应该让right左移如果numbers[left] numbers[right] target说明左侧值太小需要增大应该让left右移如果相等直接返回结果deftwoSum(numbers,target):left,right0,len(numbers)-1whileleftright:cur_sumnumbers[left]numbers[right]ifcur_sumtarget:return[left1,right1]elifcur_sumtarget:right-1else:left1return[]# 无解题目保证有解这里是防御性编程时间复杂度O ( n ) O(n)O(n)空间复杂度O ( 1 ) O(1)O(1)3.4 核心思想图解初始状态 [2, 7, 11, 15] target 9 ↑ ↑ left right 2 15 17 9right 左移 [2, 7, 11, 15] target 9 ↑ ↑ left right 2 11 13 9right 继续左移 [2, 7, 11, 15] target 9 ↑ ↑ left right 2 7 9 target找到答案 返回 [1, 2]3.5 复杂度分析解法时间复杂度空间复杂度暴力双重循环O ( n 2 ) O(n^2)O(n2)O ( 1 ) O(1)O(1)对撞指针O ( n ) O(n)O(n)O ( 1 ) O(1)O(1)对撞指针的精妙之处在于每次移动指针我们都有明确的理由当前和太大或太小避免了无效的枚举。四、LeetCode 283移动零4.1 题目分析给定一个数组nums编写一个函数将所有0移动到数组的末尾同时保持非零元素的相对顺序。必须在原地操作不使用额外的数组空间且最小化操作次数。关键约束原地操作不能创建新数组保持非零元素的相对顺序最小化操作次数4.2 问题建模这个问题可以这样思考我们要将数组分成两部分——非零区域和零区域。非零区域内的元素应该保持原有顺序零区域位于数组末尾。如何实现我们需要快慢指针快指针fast用于遍历数组寻找非零元素慢指针slow标记下一个非零元素应该放置的位置4.3 算法实现defmoveZeroes(nums):slow0forfastinrange(len(nums)):ifnums[fast]!0:nums[slow]nums[fast]ifslow!fast:# 避免将0覆盖成0或者最后统一处理nums[fast]0slow1或者更清晰的版本将交换操作分开defmoveZeroes(nums):slow0forfastinrange(len(nums)):ifnums[fast]!0:nums[slow],nums[fast]nums[fast],nums[slow]slow14.4 核心思想图解初始状态 [0, 1, 0, 3, 12] ↑ ↑ slow fast fast1 找到非零交换 nums[slow] 和 nums[fast] [1, 0, 0, 3, 12] ↑ ↑ slow fast fast2 是0跳过 fast3 找到非零交换 [1, 3, 0, 0, 12] ↑ ↑ slow fast fast4 找到非零交换 [1, 3, 12, 0, 0] ↑ ↑ slow fast 完成所有非零元素在左边保持了相对顺序4.5 复杂度分析指标数值时间复杂度O ( n ) O(n)O(n)每个元素最多被访问两次fast遍历和可能的交换空间复杂度O ( 1 ) O(1)O(1)原地操作4.6 变形与扩展变形题1不保持相对顺序如果不需要保持非零元素顺序可以直接用冒泡思想把所有0冒泡到末尾defmoveZeroes_v2(nums):nlen(nums)foriinrange(n):forjinrange(n-i-1):ifnums[j]0andjn-i-1:nums[j],nums[j1]nums[j1],nums[j]变形题2统计处理如果要同时统计0的个数可以在遍历时直接覆盖defmoveZeroes_count(nums):count0pos0fornuminnums:ifnum!0:nums[pos]num pos1else:count1nums[pos:][0]*count五、LeetCode 344反转字符串5.1 题目分析编写一个函数其作用是反转字符串。输入字符串以字符数组s的形式给出。不要给另外的数组分配额外的空间你必须原地修改输入数组使用O ( 1 ) O(1)O(1)的额外空间完成操作。这是对撞指针的典型应用场景。5.2 对撞指针实现defreverseString(s):left,right0,len(s)-1whileleftright:s[left],s[right]s[right],s[left]left1right-15.3 图解过程初始状态[h, e, l, l, o] ↑ ↑ left right 交换 h 和 o[o, e, l, l, h] ↑ ↑ left right left, right--继续交换 [o, e, l, l, h] ↑ ↑ left right 交换 e 和 l[o, l, l, e, h] left right停止 结果[o, l, l, e, h]5.4 边界情况处理defreverseString(s): 反转字符数组 left,right0,len(s)-1whileleftright:s[left],s[right]s[right],s[left]left1right-1代码简洁的关键点while left right确保我们不会重复交换或越界原地交换不需要额外空间时间复杂度O ( n ) O(n)O(n)空间复杂度O ( 1 ) O(1)O(1)六、三道题目的对比与总结6.1 模式对比题目双指针类型核心思想关键点两数之和II对撞指针从两端向中间收缩利用有序性快速排除移动零快慢指针慢指针标记目标位置原地重排反转字符串对撞指针对称位置交换边界条件 left right6.2 共同特征虽然三道题看起来不同但它们有共同的核心思想空间换时间的思想通过额外的指针信息避免重复扫描有序性利用两数之和II利用数组有序移动零和反转字符串利用索引的有序性原地操作三道题都满足O ( 1 ) O(1)O(1)空间复杂度要求6.3 双指针选择策略是否使用双指针 ├── 数组/链表是否有序 │ ├── 是 → 考虑对撞指针 │ └── 否 → 能否排序后使用 │ ├── 是否需要原地操作/重排 │ ├── 是 → 考虑快慢指针 │ └── 否 → 可能需要其他数据结构 │ └── 是否有对称操作需求 └── 是 → 考虑对撞指针6.4 复杂度模板# 对撞指针模板deftwo_pointers_opposite(arr):left,right0,len(arr)-1whileleftright:# 处理 left 和 rightifcondition:left1else:right-1# 快慢指针模板deffast_slow_pointers(arr):slow0forfastinrange(len(arr)):ifcondition:arr[slow]arr[fast]slow1七、常见错误与调试技巧7.1 对撞指针常见错误循环条件错误# 错误left right 可能导致重复比较whileleftright:# ...# 正确whileleftright:# ...忘记处理边界# 空数组或单元素数组ifnotnumbersorlen(numbers)2:return[]7.2 快慢指针常见错误slow 和 fast 移动不同步# 错误slow 只在找到非零时移动但可能多次不移动ifnums[fast]!0:nums[slow]nums[fast]slow1# fast 在循环中自然移动忘记处理最后的位置# 如果需要将后面置零要有明确逻辑foriinrange(slow,len(nums)):nums[i]07.3 调试技巧打印中间状态在关键位置打印指针位置和数组状态画图验证特别是对撞指针画图能清晰看出移动逻辑边界测试空数组、单元素数组、全部相同元素、全部零八、进阶预告双指针的基础模式并不难理解但在实际面试中面试官往往不会直接考察这么简单的问题。真正的挑战在于如何将问题建模为双指针看到一道新题如何快速识别双指针的适用性去重处理当数组包含重复元素时如何避免结果重复多维扩展三数之和、四数之和如何用双指针解决这些问题我们将在下一篇文章《双指针进阶三数之和与四数之和》中详细讨论。九、课后练习LeetCode 977有序数组的平方给定一个按非递减顺序排序的整数数组nums返回每个数字的平方组成的新数组要求也按非递减顺序排序。LeetCode 26删除有序数组中的重复项原地修改数组删除重复项使每个元素只出现一次返回新长度。LeetCode 27移除元素原地移除所有数值等于val的元素返回新长度。十、总结本文通过三道经典题目系统讲解了双指针的两种基础模式对撞指针适用于有序数组从两端向中间收缩时间复杂度O ( n ) O(n)O(n)快慢指针适用于原地操作类问题慢指针标记目标位置时间复杂度O ( n ) O(n)O(n)掌握这些基础模式理解其背后的核心思想减少无效枚举将为后续学习更复杂的问题打下坚实基础。下一篇文章我们将进入双指针的进阶领域探讨如何处理包含重复元素的去重问题以及如何将双指针与哈希表等其他技巧结合使用。推荐阅读双指针进阶三数之和与四数之和哈希表专题总结