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的位置高度为1，right位置高度为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 + 1，right = nums.length - 1。

然后分别给这三个位置进行相加，如果得到的值比0大，因为数组是排序过的，所以可以通过right右移的方式来减小三个数的和，比0小就右移left来增大三个数的和，知道left和right相遇，记录这个过程中和为0的情况。

当出现和为0的情况，就可以同时移动左右指针了。具体代码如下：

class Solution { public List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> 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.当找到sum=0的情况完成记录后，如果左指针和它的右侧或者右指针和它的左侧值是相等的情况，那就直接移动左右指针，跳过重复的情况。

4.接雨水

首先我们要知道每个位置它能够接到的雨水是多少，这个取决有该位置左侧和右侧的最大高度，如下如所示：

标红区域能够接的雨水的量和它的左右两侧有关，左侧最大高度是2，右侧最大高度是3，那么能够接到的雨水的就是左右两侧中的最小值与当前位置高度的差值，因为宽度是1，所以就不需要考虑宽度，只进行长度的减法就可以，也就是2 - 0 = 2。

这样，我们就可以使用双指针来解决这道题目，这里给定输入数组为heights，就定义left = 0，right = 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) areaTotal+=leftMax - height[left++]; else areaTotal+=rightMax - height[right--]; } return areaTotal; } }