【LeetCode】双指针专项合集

前言本章练习双指针左右碰撞指针目的掌握左右指针向中间移动最终相会的解法。在下面这几道题中思考不同题目中指针移动逻辑有什么区别125验证回文串题目要求判断一个字符串是否是回文串有两个条件限制1.忽略大小写2.忽略非字母和数字核心思路用双指针左右夹逼流程图1.left 从左开始2.right 从右开始3.跳过非字母/数字4.比较转小写后是否相等不等 → false相等 → 继续代码实现intleft0,rights.length()-1;while(leftright){//跳过非字母数字while(leftright!Character.isLetterOrDigit(s.charAt(left))){left;}while(leftright!Character.isLetterOrDigit(s.charAt(right))){right--;}//比较部分if(Character.toLowerCase(s.charAt(left))!Character.toLowerCase(s.charAt(right))){returnfalse;}left;right--;}returntrue;总结理解本题流程先跳过非字母数字再进行比较不看大小写Character.isLetterOrDigit去除非字母数字Character.toLowerCase忽略大小写344反转字符串题目要求反转字符串条件限制必须原地修改不能开新数组代码实现intleft0,rights.length-1;while(leftright){chartemps[left];s[right]s[left];s[right]temp;left;right--;}总结无15三数之和题目要求找出数组中所有和为 0 的三元组核心思路排序 固定一个数 双指针找另外两个流程1.先排序方便去重使用双指针2.固定第一个数i使得nums[left]nums[right]-nums[i]3.双指针找剩下两个数lefti1, rightn-1sum0 leftsum0 right–;sum0 正确4.去重i去重/left /和right 去重(避免造成结果一致)代码实现classSolution{publicListListIntegerthreeSum(int[]nums){ListListIntegerresnewArrayList();Arrays.sort(nums);for(inti0;inums.length;i){// 去重if(i0nums[i]nums[i-1])continue;intlefti1;intrightnums.length-1;while(leftright){intsumnums[i]nums[left]nums[right];if(sum0){left;}elseif(sum0){right--;}else{res.add(Arrays.asList(nums[i],nums[left],nums[right]));// 去重只在找到答案后while(leftrightnums[left]nums[left1])left;while(leftrightnums[right]nums[right-1])right--;left;right--;}}}returnres;}}总结思路固定一个i用双指针找到符合条件的一组答案题目要求不含重复说明我们还需要进行去重操作977有序数组的平方题目要求给你一个“已经排好序”的数组可能有负数返回每个数的平方并且结果也要有序核心思路双指针从两边往 中间选“大的平方”判断左平方与右平方的大小讲大的放入代码实现publicint[]sortedSquares(int[]nums){intnnums.length;int[]resnewint[n];intleft0,rightn-1;intindexn-1;while(leftright){intlnums[left]*nums[left];intrnums[right]*nums[right];if(lr){res[index]l;left;}else{res[index]r;right--;}index--;}returnres;}11盛水最多的容器题目要求给你是个数组height每个数代表了一根柱子的高度需求选两根柱子装最多的水核心思路双指针从中间往两边移计算完面积移动短的那一边面积的大小主要受最短边的影响left 0, right n - 1计算面积更新最大值移动较小的一边重复直到相遇代码实现intleft0,rightheight.length-1;intmax0;while(leftright){inthMath.min(height[left],height[right]);intwright-left;if(height[left]height[right]){left;}else{right--;}}returnmax;总结寻找最短边算面积想到双指针的运用42接雨水题目要求给你一个数组 height表示每个柱子的高度需求下雨之后能接多少水核心思路最多能接多少水公式当前能接水 min(左最大, 右最大) - 当前高度代码实现intleft0,rightheight.length-1;intleftMax0,maxRight0;intres0;while(leftright){if(height[left]height[right]){leftMaxMath.min(leftMax,height[left]);resleftMax-height[left];left;}else{rightMaxMath.min(rightMax,height[height]){resrightMax-height[right];right--;}}returnres;理解本题res结果的计算是通过每一小格盛水量相加得到的。并不是像上一题一样一块一块进行计算。每一格的容量是min(左墙, 右墙) - 自己高度本章总结双指针专项练习我们做了六道题本质只有三类1.对称处理两边往中间2.查找组合固定夹逼三数之和3.利用单调性(谁小动谁)我们在面对上指针题目时首先要搞清楚指针什么时候动例如三数之和 sum 0 → leftsum 0 → right–盛最多水的容器谁是最短边动谁接雨水谁小算谁leftMax / rightMax双指针的灵魂不是“两个指针”而是利用问题的“单调性 / 对称性 / 约束关系”来安全地缩小搜索范围