双指针算法详解与LeetCode经典题解

1. 双指针算法核心思想解析双指针算法Two Pointers Technique是算法竞赛和面试中最常用的优化技巧之一其核心在于通过维护两个指针索引来高效解决问题。根据指针移动方式的不同可以分为三种经典模式1.1 快慢指针模式快指针fast和慢指针slow以不同速度遍历数据结构典型应用包括链表环检测Floyd判圈算法寻找链表中点解决滑动窗口问题# 链表环检测示例 def hasCycle(head): slow fast head while fast and fast.next: slow slow.next fast fast.next.next if slow fast: return True return False1.2 对撞指针模式左右指针从两端向中间移动适用于有序数组的搜索和统计两数之和问题回文字符串验证盛水容器问题# 两数之和II示例 def twoSum(numbers, target): left, right 0, len(numbers)-1 while left right: sum_val numbers[left] numbers[right] if sum_val target: return [left1, right1] elif sum_val target: left 1 else: right - 11.3 分离指针模式两个指针分别遍历不同数组/序列常用于归并排序的合并操作判断子序列问题数组交集问题关键技巧指针移动条件的选择直接影响算法效率通常需要结合问题特点设计移动策略2. LeetCode经典四题深度剖析2.1 移动零#283问题描述将数组中的所有0移动到末尾保持非零元素相对顺序解法思路快慢指针初始化在起点快指针探索非零元素慢指针标记待交换位置def moveZeroes(nums): slow 0 for fast in range(len(nums)): if nums[fast] ! 0: nums[slow], nums[fast] nums[fast], nums[slow] slow 1复杂度分析时间复杂度O(n)空间复杂度O(1)常见误区直接删除0后补零破坏原数组使用额外数组不符合空间要求2.2 盛最多水的容器#11问题描述找出两条垂直线使得它们与x轴构成的容器可以容纳最多的水优化解法初始化左右指针在数组两端计算当前面积并更新最大值移动较短边的指针def maxArea(height): left, right 0, len(height)-1 max_area 0 while left right: area min(height[left], height[right]) * (right - left) max_area max(max_area, area) if height[left] height[right]: left 1 else: right - 1 return max_area数学证明 移动较长边不可能得到更大面积因为宽度必然减小高度受限于较短板2.3 三数之和#15问题描述找出数组中所有不重复的三元组满足abc0解题步骤数组排序O(nlogn)固定一个数转化为两数之和问题使用对撞指针寻找匹配对def threeSum(nums): nums.sort() res [] for i in range(len(nums)-2): if i 0 and nums[i] nums[i-1]: continue left, right i1, len(nums)-1 while left right: s nums[i] nums[left] nums[right] if s 0: left 1 elif s 0: right - 1 else: res.append([nums[i], nums[left], nums[right]]) while left right and nums[left] nums[left1]: left 1 while left right and nums[right] nums[right-1]: right - 1 left 1 right - 1 return res去重技巧主循环跳过相同元素找到解后跳过相同左右元素2.4 接雨水#42问题描述计算柱子排列能接多少雨水双指针解法维护左右最大高度从较小高度侧开始计算动态更新最大高度def trap(height): left, right 0, len(height)-1 left_max right_max 0 res 0 while left right: if height[left] height[right]: left_max max(left_max, height[left]) res left_max - height[left] left 1 else: right_max max(right_max, height[right]) res right_max - height[right] right - 1 return res算法对比方法时间复杂度空间复杂度适用场景暴力法O(n²)O(1)不推荐动态规划O(n)O(n)通用双指针O(n)O(1)最优单调栈O(n)O(n)需要详细分布时3. 双指针算法进阶技巧3.1 边界条件处理常见边界问题及解决方案空输入处理if not nums: return 0单元素/双元素检查if len(nums) 3: return []指针越界预防while left right and nums[left] nums[left1]:3.2 指针移动策略优化四种典型移动模式固定步长移动如每次1条件跳转移动如跳到下一个不同元素二分移动在有序数据中动态调整移动根据计算结果3.3 多指针协同问题复杂场景下的指针应用# 四数之和问题示例 def fourSum(nums, target): nums.sort() res [] for i in range(len(nums)-3): if i 0 and nums[i] nums[i-1]: continue for j in range(i1, len(nums)-2): if j i1 and nums[j] nums[j-1]: continue left, right j1, len(nums)-1 while left right: total nums[i] nums[j] nums[left] nums[right] if total target: left 1 elif total target: right - 1 else: res.append([nums[i], nums[j], nums[left], nums[right]]) while left right and nums[left] nums[left1]: left 1 while left right and nums[right] nums[right-1]: right - 1 left 1 right - 1 return res4. 实战问题排查指南4.1 常见错误类型错误现象原因分析解决方案死循环指针移动条件缺失检查循环终止条件结果遗漏指针跳过有效解添加打印调试输出顺序错误指针移动方向不当验证排序是否必要重复解去重逻辑不完善增加相邻元素比较边界值错误特殊输入未处理添加前置检查4.2 调试技巧可视化追踪法print(fStep {step}: left{left}, right{right}, nums{nums})断点条件设置if left 3 and right 5: # 设置条件断点 import pdb; pdb.set_trace()小规模测试法assert moveZeroes([0,1,0,3,12]) [1,3,12,0,0]4.3 性能优化策略提前终止条件if nums[i] 0: break # 三数之和优化冗余计算消除# 预计算前缀最大值数组 left_max [0] * len(height) left_max[0] height[0] for i in range(1, len(height)): left_max[i] max(height[i], left_max[i-1])空间复用技巧# 使用输入数组存储中间结果 nums[slow] nums[fast]在实际刷题过程中我发现双指针类问题的解题速度与对问题模式的识别能力直接相关。建议将同类问题集中训练培养对指针移动策略的直觉判断。对于hard难度的问题通常需要结合其他算法思想如贪心、动态规划才能得到最优解。