双指针基础原理与题目说明

双指针基础原理与题目说明文章目录双指针基础原理与题目说明专栏文章一、 什么是双指针算法二、 常见类型与标准模板2.1 左右指针相向双指针 / Two Ends2.2 快慢指针同向双指针 / Slow Fast三、 快慢/同向双指针应用[283. 移动零](https://leetcode.cn/problems/move-zeroes/)四、 左右/相向双指针应用[11. 盛最多水的容器](https://leetcode.cn/problems/container-with-most-water/)[15. 三数之和](https://leetcode.cn/problems/3sum/)[42. 接雨水](https://leetcode.cn/problems/trapping-rain-water/)[189. 轮转数组](https://leetcode.cn/problems/rotate-array/)[234. 回文链表](https://leetcode.cn/problems/palindrome-linked-list/)五、 双序列/链表指针应用[21. 合并两个有序链表](https://leetcode.cn/problems/merge-two-sorted-lists/)[2. 两数相加](https://leetcode.cn/problems/add-two-numbers/)[4. 寻找两个正序数组的中位数](https://leetcode.cn/problems/median-of-two-sorted-arrays/)六、 双指针与其他算法的巧妙结合[238. 除了自身以外数组的乘积](https://leetcode.cn/problems/product-of-array-except-self/) (前后缀指针)[101. 对称二叉树](https://leetcode.cn/problems/symmetric-tree/) (DFS递归 镜像双指针)[131. 分割回文串](https://leetcode.cn/problems/palindrome-partitioning/) (回溯 左右指针) 查看完整专栏LeetCode基础算法专栏专栏文章点击阅读Python 数据结构与语法速查笔记点击阅读哈希表基础原理与题目说明点击阅读双指针基础原理与题目说明点击阅读滑动窗口基础原理与题目说明点击阅读队列与单调队列基础原理与题目说明点击阅读二分查找基础原理与题目说明点击阅读矩阵基础原理与题目说明特别说明本文为个人的 LeetCode 刷题与学习笔记内容仅供学习与交流使用禁止转载或用于商业用途。需要强调的是文中的题目解法不一定是最优解可能存在时间或空间复杂度的进一步优化空间主要目的是分享个人的解题思路与逻辑实现仅供参考。笔记内容为个人理解与总结可能存在疏漏或偏差欢迎读者自行甄别并交流探讨。一、 什么是双指针算法双指针Two Pointers是一种核心的算法技巧通过在序列数组、字符串或链表中维护两个指针通常是慢指针和快指针、左右指针或者双序列指针来减少不必要的重复遍历从而大幅提高算法效率。常用于解决以下问题有序数组 / 链表问题子数组 / 子序列问题回文字符串判断 / 数组原地翻转滑动窗口问题本质是同向双指针合并区间 / 两数之和 / 三数之和 / 接雨水等核心思想两个指针同时遍历或从两端向中间靠拢。根据题意设定的条件动态移动指针避免嵌套循环将O ( n 2 ) O(n^2)O(n2)优化为O ( n ) O(n)O(n)。利用指针之间的相对位置与滑动状态判断问题结果。二、 常见类型与标准模板2.1 左右指针相向双指针 / Two Ends通常用于有序数组或字符串。左指针l从左向右右指针r从右向左根据条件移动l或r直到两者相遇。典型应用区间翻转Reverse核心逻辑就是标准左右指针交换模板l指向当前区间左端r指向右端。条件while l r保证每对元素只交换一次。defreverse(nums,l,r):whilelr:# 原地交换nums[l],nums[r]nums[r],nums[l]l1r-1通用左右指针模板l,r0,len(arr)-1whilelr:# 根据问题逻辑处理 arr[l], arr[r]ifcondition1:l1elifcondition2:r-1else:# 视情况可能同时移动l1r-12.2 快慢指针同向双指针 / Slow Fast常用于链表或数组原地修改。快指针走得快如探路者慢指针走得慢如收集者。slowfaststart_pointwhilefastandfast.next:slowslow.nextfastfast.next.next# 例如判断环形链表ifslowfast:break三、 快慢/同向双指针应用283. 移动零题目描述给定一个数组nums编写一个函数将所有0移动到数组的末尾同时保持非零元素的相对顺序。必须在不复制数组的情况下原地对数组进行操作。解题思路选用同起点双指针交换法。填充指针l标记下一个非零元素要填充的位置遍历指针r逐个扫描寻找非零元素。通过原地交换将非零元素按原始相对顺序“筛选”到前端零元素自然归位到后端。核心代码fromtypingimportListclassSolution:defmoveZeroes(self,nums:List[int])-None: 核心思路双指针均从0起步非零元素换至前端零自然退至后端 l,r0,0nlen(nums)whilern:# 找到非零元素时将其交换到 l 指向的位置ifnums[r]!0:nums[l],nums[r]nums[r],nums[l]l1# 遍历指针持续右移r1四、 左右/相向双指针应用11. 盛最多水的容器题目描述给定一个长度为n的整数数组height找出其中的两条线使得它们与 x 轴共同构成的容器可以容纳最多的水。解题思路初始定位在两端宽度最大。盛水面积 指针间距宽度 × 较矮的高度。因此每次始终移动高度较矮的指针牺牲宽度以换取寻找更高边界的可能。核心代码fromtypingimportListclassSolution:defmaxArea(self,height:List[int])-int:l,r0,len(height)-1ans0whilelr:ifheight[l]height[r]:cur(r-l)*height[l]l1# 移动更矮的左指针else:cur(r-l)*height[r]r-1# 移动更矮的右指针ansmax(ans,cur)returnans15. 三数之和题目描述给你一个整数数组nums判断是否存在三元组和为 0。请你返回所有和为 0 且不重复的三元组。解题思路排序 双指针法。外层循环固定一个数内层将剩余空间转化为“两数之和等于其相反数”的问题。利用升序数组特性移动左右指针j和k同时注意过滤相邻重复元素以达到去重目的。核心代码fromtypingimportListclassSolution:defthreeSum(self,nums:List[int])-List[List[int]]:ans[]nums.sort()# 排序是去重与双指针移动的基础foriinrange(len(nums)):# 去重跳过 i 的重复值ifi0andnums[i]nums[i-1]:continuetarget-nums[i]klen(nums)-1forjinrange(i1,len(nums)):# 去重跳过 j 的重复值ifji1andnums[j]nums[j-1]:continue# 和过大则左移 k缩小数值whilejkandnums[j]nums[k]target:k-1ifjk:breakifnums[j]nums[k]target:ans.append([nums[i],nums[j],nums[k]])returnans42. 接雨水题目描述给定n个非负整数表示柱子的高度图计算按此排列的柱子下雨之后能接多少雨水。解题思路单个位置接水量由「左右两侧最大高度的较小值」决定。双指针从两端向中间移动实时维护left_max和right_max。由当前较矮的一侧决定实际接水高度计算完毕后向中间逼近。核心代码fromtypingimportListclassSolution:deftrap(self,height:List[int])-int:ans0l,r0,len(height)-1left_maxright_max0whilelr:left_maxmax(left_max,height[l])right_maxmax(right_max,height[r])# 由较矮的一侧决定接水量ifheight[l]height[r]:ans(left_max-height[l])l1else:ans(right_max-height[r])r-1returnans189. 轮转数组题目描述给定一个整数数组nums将数组中的元素向右轮转k个位置。解题思路通过三次翻转实现原地右旋。基于前面提到的reverse左右指针交换模板先翻转整个数组再翻转前k mod n个元素最后翻转剩余元素。核心代码fromtypingimportListclassSolution:defrotate(self,nums:List[int],k:int)-None:nlen(nums)indexk%ndefreverse(l,r):whilelr:nums[l],nums[r]nums[r],nums[l]l1r-1# 1. 翻转全部reverse(0,n-1)# 2. 翻转前段 [0, (k mod n)-1]reverse(0,index-1)# 3. 翻转后段 [k mod n, n-1]reverse(index,n-1)234. 回文链表解题思路利用「数组可随机访问」的特性先将链表元素按序存入数组。随后使用经典的左右指针从数组两端向中间靠拢对比元素是否一致。fromtypingimportOptional# class ListNode:# def __init__(self, val0, nextNone):# self.val val# self.next nextclassSolution:defisPalindrome(self,head:Optional[ListNode])-bool:listarray[]currentheadwhilecurrent:listarray.append(current.val)currentcurrent.nextnlen(listarray)l,r0,n-1whilelr:iflistarray[l]!listarray[r]:returnFalsel1r-1returnTrue五、 双序列/链表指针应用处理两个独立的序列或链表时通常需要维护两个独立的遍历指针比较后进行逻辑流转。21. 合并两个有序链表解题思路使用双指针虚拟头节点。逐节点比较两个链表的当前值优先拼接更小值的节点以保证升序。循环结束后将未遍历完的链表直接追加到尾部。核心代码fromtypingimportOptionalclassSolution:defmergeTwoLists(self,list1:Optional[ListNode],list2:Optional[ListNode])-Optional[ListNode]:dummycur_nodeListNode(0)whilelist1andlist2:iflist1.vallist2.val:cur_node.nextlist1 list1list1.nextelse:cur_node.nextlist2 list2list2.nextcur_nodecur_node.next# 拼接剩余节点cur_node.nextlist1iflist1elselist2returndummy.next2. 两数相加解题思路逆序存储天然匹配从个位开始相加的逻辑。设置两个指针同步遍历链表同时维护一个carry进位标记。空节点按 0 处理直至两链表遍历完且进位为 0 时终止。核心代码fromtypingimportOptionalclassSolution:defaddTwoNumbers(self,l1:Optional[ListNode],l2:Optional[ListNode])-Optional[ListNode]:dummycurListNode(0)carry0whilel1orl2orcarry:val1l1.valifl1else0val2l2.valifl2else0totalval1val2carry cur_valtotal%10carrytotal//10cur.nextListNode(cur_val)curcur.nextifl1:l1l1.nextifl2:l2l2.nextreturndummy.next4. 寻找两个正序数组的中位数解题思路通过双指针将两个有序数组合并为一个完整的升序数组。谁更小就把谁加入合并数组最后根据合并数组的长度奇偶性计算中位数。(注严格要求的O ( log ⁡ ( m n ) ) O(\log (mn))O(log(mn))需使用二分查找此处合并法的时间复杂度为O ( m n ) O(mn)O(mn)胜在逻辑直观适合作为基础掌握)核心代码fromtypingimportListclassSolution:deffindMedianSortedArrays(self,nums1:List[int],nums2:List[int])-float:nums[]idx1,idx20,0# 合并过程whileidx1len(nums1)andidx2len(nums2):ifnums1[idx1]nums2[idx2]:nums.append(nums1[idx1])idx11else:nums.append(nums2[idx2])idx21# 追加剩余元素nums.extend(nums1[idx1:])nums.extend(nums2[idx2:])nlen(nums)ifn%21:returnnums[n//2]else:left,rightn//2-1,n//2return(nums[left]nums[right])/2六、 双指针与其他算法的巧妙结合238. 除了自身以外数组的乘积 (前后缀指针)解题思路利用左右双向遍历维护两个列表或直接利用输出数组进行优化分别存储当前节点左边的乘积和右边的乘积最终相乘。避免了使用除法导致的零位异常。核心代码fromtypingimportListclassSolution:defproductExceptSelf(self,nums:List[int])-List[int]:nlen(nums)left_ans[1]*n right_ans[1]*n ans[0]*nforlinrange(1,n):left_ans[l]left_ans[l-1]*nums[l-1]forrinrange(n-2,-1,-1):right_ans[r]right_ans[r1]*nums[r1]foriinrange(n):ans[i]left_ans[i]*right_ans[i]returnans101. 对称二叉树 (DFS递归 镜像双指针)解题思路初始化两个指针均指向根节点在 DFS 递归验证时保持“左指针向左右指针向右”的镜像移动规则。重点控制双空、单空及值不等时的终止条件。核心代码fromtypingimportOptional# class TreeNode:# def __init__(self, val0, leftNone, rightNone):# self.val val# self.left left# self.right rightclassSolution:defisSymmetric(self,root:Optional[TreeNode])-bool:ifrootisNone:returnTruedefcheck(l:Optional[TreeNode],r:Optional[TreeNode])-bool:iflisNoneandrisNone:returnTrueiflisNoneorrisNone:returnFalseifl.valr.val:left_checkcheck(l.left,r.right)right_checkcheck(l.right,r.left)returnTrueifleft_checkandright_checkelseFalseelse:returnFalsereturncheck(root,root)131. 分割回文串 (回溯 左右指针)解题思路start索引控制分割起点i遍历控制终点。在尝试切分时抽离出一个辅函数使用双指针判断子串是否为回文串。如果是才做选择并继续向下一层递归剪枝操作。核心代码fromtypingimportListclassSolution:defpartition(self,s:str)-List[List[str]]:res[]path[]defishuiwen(left,right):whileleftright:ifs[left]!s[right]:returnFalseleft1right-1returnTruedefbacktrack(start):ifstartlen(s):res.append(path.copy())returnforiinrange(start,len(s)):ifishuiwen(start,i):path.append(s[start:i1])backtrack(i1)path.pop()backtrack(0)returnres