hot100-双指针

1.移动零利用快慢指针数值的交换来移动所有的0首先快慢指针都在起始位置快指针不断地向前移动当快指针发现这个位置不是0那么就跟慢指针的位置去做交换慢指针向后移动一个位置这样一点一点的把0移动到后面。具体的过程参考下面的下图。这里就不展示整个过程否则图片过长就是通过这种方式让非0元素移动到前面0元素移动到后面。具体实现如下class Solution { public void moveZeroes(int[] nums) { int slow 0; for (int fast 0; fast nums.length; fast){ if (nums[fast]!0){ swapNum(nums,slow,fast); slow; } } } private void swapNum(int[] nums, int slow, int fast) { int temp nums[slow]; nums[slow] nums[fast]; nums[fast] temp; } }2.盛水最多的容器可以在左右两侧各放一个指针然后利用贪心的思路每次都记录最大面积然后移动左右指针比较小的直到左右指针重合。这里是只能去移动左右指针中较小的一个的因为如果移动大的那一个无论下一个元素是更大还是更小都不会让这个面积更大。这里可以稍作演示假设left的位置高度为1right位置高度为5之间距离也是5那么此时它的之间容纳的最大容量也就是1 * 5 5。现在我要移动右指针right哪怕right移动后变成10那么因为做指针比较小所以右指针再大也没有相反因为距离变短还导致容积减少了。如果right移动后变小了那么有可能会变得比left位置还要小那么高度宽度都减小容量就更小了因此必须移动左右指针中较小的那个指针。具体代码如下class Solution { public int maxArea(int[] height) { int max 0; int left 0; int right height.length - 1; while (left right){ int w Math.min(height[left],height[right]); int h right - left; max Math.max(max,w * h); if (height[left] height[right]) left; else right--; } return max; } }3.三数之和这里可以先给数组进行排序然后在遍历数组过程中每次循环都创建左右两个指针比如当前遍历到i的位置两个指针left i 1right nums.length - 1。然后分别给这三个位置进行相加如果得到的值比0大因为数组是排序过的所以可以通过right右移的方式来减小三个数的和比0小就右移left来增大三个数的和知道left和right相遇记录这个过程中和为0的情况。当出现和为0的情况就可以同时移动左右指针了。具体代码如下class Solution { public ListListInteger threeSum(int[] nums) { ListListInteger result new ArrayList(); Arrays.sort(nums); for (int i 0; i nums.length; i){ if (i 0 nums[i] nums[i - 1]) continue; if (nums[i] 0) return result; int left i 1; int right nums.length - 1; while (left right){ int sum nums[i] nums[left] nums[right]; if (sum 0) right--; else if (sum 0) left; else { result.add(List.of(nums[i],nums[left],nums[right])); while (left right nums[left] nums[left 1]) left; while (left right nums[right] nums[right - 1]) right--; left; right--; } } } return result; } }代码中是做了一点剪枝操作来减少运行时间以及需要进行去重操作。1.因为数组是排序之后的所以如果遍历过程中发现这个位置的数字已经大于0了那就没有遍历下去的因为left和right位置肯定比i位置的值更大。2.当前位置的数字和上一个位置相同也是没有往下进行的。比如下面这个例子数组nums为[-2,-2,0,2]那么nums[1]这个位置遍历结果适合nums[0]完全一样的因为题目返回的是数字而不是下标。3.当找到sum0的情况完成记录后如果左指针和它的右侧或者右指针和它的左侧值是相等的情况那就直接移动左右指针跳过重复的情况。4.接雨水首先我们要知道每个位置它能够接到的雨水是多少这个取决有该位置左侧和右侧的最大高度如下如所示标红区域能够接的雨水的量和它的左右两侧有关左侧最大高度是2右侧最大高度是3那么能够接到的雨水的就是左右两侧中的最小值与当前位置高度的差值因为宽度是1所以就不需要考虑宽度只进行长度的减法就可以也就是2 - 0 2。这样我们就可以使用双指针来解决这道题目这里给定输入数组为heights就定义left 0right heights.length - 1。同时我们用两个变量来记录当前状态下左右两侧的最大值leftMax heights[0]和rightMax heights[heights.length - 1]。如图所示当left和right在左右两侧时当前能够知道的左侧最大值为0右侧最大值为1右侧真正的最大值当前未知因为我们还没有遍历到中间的位置但是并不影响我们来判断left位置的雨水容量因为左侧的最大值只能是0右侧再大也不会影响最终在容纳雨水的量因此left位置的容量也就是0 - 0 0。完成之后让left右移更新leftMax的值。右侧也是同理的我们能够知道当前位置右侧的最大值但不清楚当前位置左侧的最大值但是只要当前位置右侧的最大值比左侧的小那么左侧即使再大也没有任何意义因为雨水容量取决于较短的那条边。过程讲解完毕下面为具体的代码class Solution { public int trap(int[] height) { int left 0; int right height.length - 1; int leftMax 0; int rightMax 0; int areaTotal 0; while (left right){ leftMax Math.max(leftMax,height[left]); rightMax Math.max(rightMax,height[right]); if (leftMax rightMax) areaTotalleftMax - height[left]; else areaTotalrightMax - height[right--]; } return areaTotal; } }