双指针经典题目解析【持续更新】

1.移动零

1.1题目链接

移动零

1.2题目解析

题目要求将所有0移动到数组末尾，同时保持非0元素的相对顺序，其实我们可以反向思考：将所有非0元素移动到数组最前面，因为题目关心的只是非0元素的顺序：我们可以定义两个下标：dest和cur，用cur来遍历整个数组，fest则表示非0元素应该被放置的位置。遇到非0元素就把它放在dest的位置 然后dest++，直到整个数组被遍历完成，那么所有的非0元素就给放在前面了。

1.3代码实现

publicvoidmoveZeroes(int[]nums){intdest=0;intcur=0;intlength=nums.length;for(cur=0;cur<length;cur++){if(nums[cur]!=0){inttmp=nums[cur];nums[cur]=nums[dest];nums[dest]=tmp;dest++;}}}

2.盛最多水的容器

2.1题目链接

盛最多水的容器

2.2题目解析

本题让求容器的最大储水水量 其实也就是求容器的最大体积，体积=宽度*高度，我们依然可以采用双指针来解这道题：定义一个left在数组最左边，right在数组最右边，它们之间的差值就是宽度，那么初始状态下体积就是差值乘以nums[left]和nums[right]的较小值，因为短板效应嘛OK，这就算出来一个体积值 ，但是不确定是不是最大，所以我们要接着算——让它们往中间走，那么是让left++还是right–呢？

精髓就在于当left或者right移动时：它们的差值一定是在减小，也就是容器的宽度，宽度减小情况下，如果我们想获得比初次更大的体积，必须让高度增加，也就是nums[left]或者nums[right]，所以让谁走很明显了：肯定是较小的那个高度走：本来你就拖后腿，只有你走了才可能换来更大的值让原来的较大值“对比”之下成为较小值，从而以高度的变动弥补宽度的减小

2.3代码实现

publicintmaxArea(int[]height){intproVolume=0;intleft=0;intlength=height.length;intright=length-1;while(left<right){//体积是由较低的高度决定的intvolume=min(height[left],height[right])*(right-left);if(volume>=proVolume){proVolume=volume;}if(height[left]<=height[right]){left++;}else{right--;}}returnproVolume;}publicintmin(inta,intb){if(a>=b){returnb;}else{returna;}}

3.三数之和

3.1题目链接

三数之和

3.2题目解析

思路并不难：我们直接遍历数组，首先固定一个数开始算出0-nums[i]的值，也就是剩下两个数相加的目标值，剩下两个数就从除去第一个数之后的区间中找【也就是两数之和的逻辑去做】。固定数从下标0开始，一直遍历到length-2的位置。

难的点在于去重：要求返回所有不重复的三元组，按照这个思路有两两个需要考虑去重的地方：i和两数之和部分，首先两数之和：可能不止有一组相加等于0-nums[i]的，比如 0 2 0 1 1，假设0-nums[i]是1，那么我们去重的处理方式就是先给数组排成正序，这样处理之后就是0 0 0 0 1 1 1 1 2，当我们找到一个符合的两元组之后， 比如0 1 ，我们可以写一个while让left一直＋直到脱离0为止，right也是同理

那么i的去重就比较简单，比如整个数组是 -1 -1 -1 0 0 0 0 0 1 1 1 1 2，i在下标0的位置，我们搞一个j=i+，如果nums[i]==nums[j]，那么i就＋＋，一直加到这个条件不成立 ，也就是i对应元素值变化而不是单纯的下标加一。

以上操作还需考虑下标越界的问题，我是图省事直接用if语句判断的。

3.3代码实现

publicstaticList<List<Integer>>threeSum(int[]nums){Arrays.sort(nums);intlength=nums.length;List<List<Integer>>answer=newArrayList<>();for(inti=0;i<length-2;i++){intleft=i+1;intright=length-1;inttarget=0-nums[i];while(left<right){if(nums[left]+nums[right]==target){List<Integer>small=newArrayList<>();small.add(nums[i]);small.add(nums[left]);small.add(nums[right]);answer.add(small);//开始移动下标(去重)while(nums[left]==small.get(1)){if(left>=right){break;}left++;}while(nums[right]==small.get(2)){if(left>=right){break;}right--;}}else{if(left>=right){break;}if(nums[left]+nums[right]>target){right--;}else{left++;}}}//给i去重intj=i+1;while(nums[i]==nums[j]){i++;j++;if(j>=length){break;}}}returnanswer;}