LeetCode算法（双指针）

今天的题目主要都是力扣前100中，关于双指针的题

1.移动零

链接：移动零

示例：

示例 :

输入: nums =[0,1,0,3,12]

输出：[1,3,12,0,0]

可以看到保持原有元素的顺序，将所有的0，移动到数组最后方即可。

这道题看见思路很明确，就是遍历数组，碰到0了，进行位置互换。这个题目实际上和数组的元素移除几乎是一样的，只不过元素删除是进行覆盖，而移动0是进行元素移动

思路：

（1）定义两个指针，一个为快指针（负责遍历数组），另一个为慢指针（负责标记0）

（2）快指针进行移动遍历，如果发现0元素，则不进行任何操作，如果不是0元素，则进行与慢指针的元素互换

代码如下：

public class MobileZero {/*移动0*///思路：双指针法//快慢指针同时移动，一个指针用于标记0，一个指针移动，非0则交换两个指针，0则继续移动public void moveZeroes(int[] nums) {//慢指针：标记非0元素的位置int slowCur = 0;//快指针：遍历数组for (int cur = 0; cur < nums.length; cur++) {if (nums[cur] != 0){int temp = nums[cur];nums[cur] = nums[slowCur];nums[slowCur] = temp;//移动慢指针slowCur++;}}}}

2.三数之和

链接：三数之和

示例：

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ]

这道题我的大概思路就是，遍历所有元素，并找到每个元素对应的两个符合条件的数字，那既然需要两个数字，就需要使用双指针了

那么下一个问题就是，指针该指向哪里，并如何移动呢？

首先就需要将数组进行排序，因为有了顺序性，才有移动的规律，当我们将数组排序后

[-4,-1,-1,0,1,2] 

遍历整个数组的所有元素，并把其当作a
三种情况：
1.a+b+c=0 这种情况符合要求，添加到列表中
2.a+b+c>0 这种情况说明，a+b<c 所以c要减小
3.a+b+c<0 这种情况说明，a+b>c 所以b要增大

换成指针来说，减小和增大就要移动，那么位置我设置的头指针指向a+1，尾指针指向数组末尾

第二种情况：尾指针向前移动

第三种情况：头指针向后移动

代码如下：

import java.util.*;public class SumOfThreeNumbers {/*三数之和*/public List<List<Integer>> threeSum(int[] nums) {//思路：a + b + c = 0//采用双指针思路，遍历所有元素，并把其当作a，然后寻找 b + c = -a 的元素//头指针指向a+1，尾指针指向数组末尾，数组排序//遍历整个数组的所有元素，寻找每个元素的对应数值//三种情况：//1.a+b+c=0 这种情况符合要求，添加到列表中//2.a+b+c>0 这种情况说明，a+b<c 所以c要减小，尾指针向前移动//3.a+b+c<0 这种情况说明，a+b>c 所以b要增大，头指针向后移动//去重处理：在进入遍历数组时，判断当前元素是否等于上一个元素，如果相等则跳过该元素的遍历//对指针进行处理：因为指针的遍历也会重复，所以采用while循环// 如果移动的下一个元素相等，那么指向下一个元素，然后进行自增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;}//在每次循环中，来移动头指针和尾指针int left = i + 1;int right = nums.length - 1;//移动指针并寻找满足条件的元素while(left < right){int num = nums[i] + nums[left] + nums[right];//满足条件if (num == 0){List<Integer> list = new ArrayList<>();list.add(nums[i]);list.add(nums[left]);list.add(nums[right]);result.add(list);//去重处理：防止指针所指向的元素重复while(left < right && nums[left] == nums[left + 1]){left++;}while(left < right && nums[right] == nums[right - 1]){right--;}//移动指针，寻找当前元素的其他对应元素left++;right--;} else if (num > 0) {//c过大，尾指针左移right--;}else {//b过小，头指针右移left++;}}}return result;}}

3.盛最多水的容器

链接：盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

示例 ：

输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

思路：

简单理解，就是寻找最大乘积，底 x 高的最大值，其实这里可以直接使用循环不去思考，双指针移动，遍历每一根柱子与其他柱子形成的底，和取两个柱子最短的进行相乘，找到最大值就好了，但是会超时，所以，又要考虑双指针的移动问题（选高柱子会漏水）

首先将问题拆分，最大值无非就是找到，底最大，高最大的值，如果我们先从高入手，那么就是将数组进行排序，可是这样，毫无规律，又要进行遍历，所以试试从底入手

那么最大底，一定是第一个柱子和最后一个柱子形成的底最大，然后比较两者谁更矮，移动指向矮的那一边的指针

因为下一个指向，如果还比最后一个柱子矮，则会继续向尾部移动寻找，如果高，尾部向头部移动。

代码如下：

import java.util.HashMap;public class TheContainerWithTheMostWaterCapacity {/*盛水最多的容器*/public int maxArea(int[] height) {//思路：定义两个指针，一个指向第一个值，一个指向最后一个值//根据索引计算底宽，根据值的大小判断高，小的做高//哪边的值小，则对应的指针移动，更新最大值int beforeCur = 0;int behindCur = height.length - 1;int maxVolume = 0;while (beforeCur < behindCur) {int bottom = behindCur - beforeCur;int high = Math.min(height[beforeCur], height[behindCur]);maxVolume = Math.max(maxVolume, bottom * high);if (height[beforeCur] > height[behindCur]) {behindCur--;} else {beforeCur++;}}return maxVolume;}}

 今天的题更多的是思路吧，比起前面的基础数据结构知识，会更复杂，更考验读题，今天的练习就到这里！谢谢大家