LeetCode Hot100 - 双指针篇
前言
挑战一个月刷完力扣的hot100，记录一下每题的思路~
这次是双指针相关的题目
（1）283. 移动零
①双指针，找第一个零和零后第一个非零数字，然后交换
class Solution {public void moveZeroes(int[] nums) {int num=0, zero=0; // 记录零后第一个数字和第一个零while(num!=nums.length){if(num<zero)num++; // 保证找到零后的非零数字else if(nums[num]==0)num++; // 找非零else if(nums[zero]!=0)zero++; // 找零else { // 交换nums[zero]=nums[num];nums[num]=0;num++;zero++;}}}
}②双指针，左指针左侧均为非零数，右指针在左指针后找第一个非零数，找到就交换
class Solution {public void moveZeroes(int[] nums) {int l=0, r=0; // 左指针左侧均非零，右指针找左指针后第一个非零数while(r<nums.length){if(nums[r]!=0){ // 找到非零数就与左指针交换int temp = nums[l];nums[l]=nums[r];nums[r]=temp;l++;}r++;}}
}（2）11. 盛最多水的容器
双指针，从左右边界开始，必定移动左右边界其中一个，对于较小的那边，不可能在产生更大的容量情况，于是丢弃该边，问题转换为新的数组边界，不断丢弃较小的边。一直保留最长边，然后迭代考虑宽度
class Solution {public int maxArea(int[] height) {int res=0, l=0, r=height.length-1;while(l<r){res=Math.max(res,(r-l)*Math.min(height[l],height[r]));// 小的那边不可能再产生更大的容量，丢弃该边，转换为新的数组边界情况if(height[l]<=height[r])l++;else r--;}return res;}
}（3）15. 三数之和
排序+双指针，先排序，迭代确定第一个数，剩下两个数使用双指针选取。注意第一个数不能重复选择，后续两个数选定后还要用while去重。
边界条件：数组长度不够、第一个数下标不大于n-2、前三个数和大于0、第一个数和最后两个数和小于零
class Solution {List<List<Integer>> res = new ArrayList<>();public List<List<Integer>> threeSum(int[] nums) {if(nums.length<3)return res; // 长度不够Arrays.sort(nums); // 排序int n = nums.length;for(int i=0;i<n-2;i++){if(nums[i]+nums[i+1]+nums[i+2]>0)break; // 最小和大于零，直接返回if(nums[i]+nums[n-2]+nums[n-1]<0)continue; // 最大和小于零，第一个数跳过if(i!=0&&nums[i]==nums[i-1])continue; // 跳过重复int l=i+1, r=n-1;while(l<r){ // 双指针寻找int sum = nums[l]+nums[r];if(sum+nums[i]<0)l++; // 和小else if(sum+nums[i]>0)r--; // 和大else { // 和为零res.add(new ArrayList<>(Arrays.asList(nums[i],nums[l],nums[r])));l++;r--;// 跳过重复while(l<r&&nums[l]==nums[l-1])l++;while(l<r&&nums[r]==nums[r+1])r--;}}}return res;}
}（4）42. 接雨水
①动规，从左到右记录左侧最高柱子，从右到左记录右侧最高柱子，计算并存储每个位置两边的最大高度，然后遍历每个位置计算接水量
class Solution {public int trap(int[] height) {int n = height.length;if(n==0)return 0;// 左侧最高柱子int[] leftMax = new int[n];leftMax[0]=height[0];for(int i=1;i<n;i++)leftMax[i]=Math.max(leftMax[i-1],height[i]);// 右侧最高柱子int[] rightMax = new int[n];rightMax[n-1]=height[n-1];for(int i=n-2;i>=0;i--)rightMax[i]=Math.max(rightMax[i+1],height[i]);// 每个位置的接水量int res=0;for(int i=0;i<n;i++)res+=Math.min(leftMax[i],rightMax[i])-height[i];return res;}
}②单调栈，栈底最大，栈只记录一次接水部分的左侧柱子。若出现出现高(left)、低(top)、高(i)情况，表示有接水出现，计算接水部分。top表示接水的低处，取top先判断左侧是否有更高柱，即left是否存在，如果不存在表示不形成接水，直接break找下一个接水部分
class Solution {public int trap(int[] height) {int res=0;Deque<Integer> stack = new ArrayDeque<>(); // 单调栈，栈底最大for(int i=0;i<height.length;i++){while(!stack.isEmpty()&&height[i]>height[stack.peek()]){int top=stack.pop(); // 低部分，先判断左侧是否有更高柱if(stack.isEmpty())break; // top左侧更高柱，不形成接水// 出现高(left)、低(top)、高(i)情况，计算接水部分int left=stack.peek();int curWidth=i-left-1; int curHeight=Math.min(height[left],height[i])-height[top];res += curWidth*curHeight;}stack.push(i);}return res;}
}③双指针，左右两个指针遍历，并记录左右已遍历的最高柱子高度。每次会移动更矮指针，因此没移动的指针为目前已遍历最高柱子，保证移动的指针处能接水，并根据移动侧的最高柱子高度计算接水量
class Solution {public int trap(int[] height) {int res=0, l=0, r=height.length-1;int maxL=0, maxR=0;while(l<r){// 记录左右已遍历的最高柱子maxL = Math.max(maxL,height[l]);maxR = Math.max(maxR,height[r]);// 每次会移动更矮指针，因此没移动的指针为目前已遍历最高柱子if(height[l]<height[r]){ // 因此r为目前最高柱子，l根据maxL蓄水res+=maxL-height[l];l++;}else{res+=maxR-height[r]; // 因此l为最高柱子，r根据maxR蓄水r--;}}return res;}
}④双指针，主要思想与③同，但判断接水条件不同，个人感觉更好理解一点。左右两个指针遍历，并记录左右已遍历的最高柱子高度。每次判断最高柱子在哪侧，即更矮侧的柱子一定跟接水，根据更矮侧的最高柱子高度蓄水
class Solution {public int trap(int[] height) {int res=0, l=0, r=height.length-1;int maxL=0, maxR=0;while(l<r){// 记录左右已遍历的最高柱子maxL = Math.max(maxL,height[l]);maxR = Math.max(maxR,height[r]);if(maxL<maxR){ // 最高柱子在右侧，l处一定能蓄水res+=maxL-height[l];l++;}else{res+=maxR-height[r]; // 最高柱子在左侧，r处一定能蓄水r--;}}return res;}
}总结
①双指针用于交换、查找指定条件的情况
②移动零，一个指针指向已判断的序列，一个指针寻找后续第一个非零数，然后交换
③盛最多水的容器，利用更小边界不会再有更大容量的特点，使用双指针不断缩小边界，找到最大容量的情况
④三数之和，先排序，迭代确定第一个数，使用双指针找到指定和的两个数。注意去重和边界条件剪枝
⑤接雨水，有三种解题方式。第一种动规，记录每个位置左右侧最高柱，然后遍历计算每个位置接水量。第二种单调栈，记录每个节水部分的左侧柱子，出现高低高时计算接水量，注意判断left不存在的情况。第三种双指针，左右两侧指针遍历，并分别记录左右最高柱高度，可理解为每次不移动的指针表示已知最高柱，另一侧接水；也可理解为直接比较最高处在哪侧，另一侧接水