文章目录283. 移动零双指针11. 盛最多水的容器双指针167. 两数之和 II - 输入有序数组双指针15. 三数之和42. 接雨水前后缀分解相向双指针总结283. 移动零283. 移动零双指针使用双指针左指针指向当前已经处理好的序列的尾部右指针指向待处理序列的头部。右指针不断向右移动每次右指针指向非零数则将左右指针对应的数交换同时左指针右移。注意到以下性质左指针左边均为非零数右指针左边直到左指针处均为零。因此每次交换都是将左指针的零与右指针的非零数交换且非零数的相对顺序并未改变。classSolution{publicvoidmoveZeroes(int[]nums){intleft0,right0;while(rightnums.length){if(nums[right]!0){inttemnums[left];nums[left]nums[right];nums[right]tem;left;}right;}}}11. 盛最多水的容器11. 盛最多水的容器双指针如果短的边界不变不管长的边界怎么向内移动容积只会变小所以每次要移动短的边界每次将对应的数字较小的那个指针往另一个指针的方向移动一个位置就表示我们认为这个指针不可能再作为容器的边界了classSolution{publicintmaxArea(int[]height){intl0,rheight.length-1;intans0;while(lr){inttemMath.min(height[l],height[r])*(r-l);ansMath.max(ans,tem);if(height[l]height[r])l;elser--;}returnans;}}167. 两数之和 II - 输入有序数组167. 两数之和 II - 输入有序数组双指针sum过大则最大数不选于是right--sum过小则最小数不选于是leftclassSolution{publicint[]twoSum(int[]numbers,inttarget){intleft0,rightnumbers.length-1;while(leftright){intsumnumbers[left]numbers[right];if(sumtarget){returnnewint[]{left1,right1};}if(sumtarget){right--;}else{left;}}returnnewint[]{};}}15. 三数之和15. 三数之和为方便双指针以及跳过相同元素先把 nums 排序。枚举 nums[i]问题变成 nums[j]nums[k]−nums[i]题目转换为167. 两数之和相似。如何避免重复三元组在外层循环中如果nums[i] nums[i−1]则跳过nums[i]直接 continue。在内层循环中当三数之和等于 0 时为避免把相同的三元组计入答案跳过后续相同的 nums[j] 和 nums[k]也可以只跳过相同的 nums[j]。classSolution{publicListListIntegerthreeSum(int[]nums){Arrays.sort(nums);//先排序成有序的ListListIntegeransnewArrayList();intnnums.length;for(inti0;in-2;i){if(i0nums[i]nums[i-1]){//nums[i]去重遇到重复直接跳过continue;}if(nums[i]nums[i1]nums[i2]0)break;//优化一if(nums[i]nums[n-1]nums[n-2]0)continue;//优化二intji1,kn-1;while(jk){intsumnums[i]nums[j]nums[k];if(sum0){j;}elseif(sum0){k--;}else{ans.add(List.of(nums[i],nums[j],nums[k]));j;while(jknums[j]nums[j-1]){//nums[j]去重j;}k--;while(kjnums[k]nums[k1]){//nums[k]去重k--;}}}}returnans;}}优化如果当前最小的三个数相加都大于0即nums[i] nums[i 1] nums[i 2] 0则说明后面的数不可能存在符合题目的直接break如果当前nums[i]加上最大的两个数还小于0即nums[i] nums[n - 1] nums[n - 2] 0则说明i太小直接跳过这个i把nums[i]用int x代替会更省时List.of() 快速打包几个元素成一个只读列表在 LeetCode 中非常常用一行代码就能返回一个列表结果42. 接雨水42. 接雨水前后缀分解先从左到右计算从0到这个位置的最大高度再从右到左计算从结尾到这个位置的最大高度然后由min(前,后) - 高度得到每个位置能接多少雨水并累加起来classSolution{publicinttrap(int[]height){intnheight.length;int[]qnewint[n];int[]hnewint[n];q[0]height[0];h[n-1]height[n-1];for(inti1;in;i){q[i]Math.max(q[i-1],height[i]);}for(intin-2;i0;i--){h[i]Math.max(h[i1],height[i]);}intans0;for(inti0;in-1;i){ansMath.min(q[i],h[i])-height[i];}returnans;}}时间复杂度O(n)空间复杂度O(n)相向双指针优化一下空间复杂度原理类似11. 盛最多水的容器classSolution{publicinttrap(int[]height){intnheight.length;intans0;intleft0;intrightn-1;intpreMax0;// 前缀最大值随着左指针 left 的移动而更新intsufMax0;// 后缀最大值随着右指针 right 的移动而更新while(leftright){preMaxMath.max(preMax,height[left]);sufMaxMath.max(sufMax,height[right]);if(preMaxsufMax){anspreMax-height[left];left;}else{anssufMax-height[right];right--;}}returnans;}}总结双指针Two Pointers通过维护两个指针的位置让两个指针按照某种规则移动从而减少不必要的遍历。传统暴力fori:forj:判断时间复杂度O(n²)双指针left → ← right两个指针共同移动时间复杂度O(n)核心不需要回头通过指针移动缩小问题范围
