283. 移动零

283. 移动零

双指针

使用双指针，左指针指向当前已经处理好的序列的尾部，右指针指向待处理序列的头部。

右指针不断向右移动，每次右指针指向非零数，则将左右指针对应的数交换，同时左指针右移。

注意到以下性质：

左指针左边均为非零数；

右指针左边直到左指针处均为零。

因此每次交换，都是将左指针的零与右指针的非零数交换，且非零数的相对顺序并未改变。

classSolution{publicvoidmoveZeroes(int[]nums){intleft=0,right=0;while(right<nums.length){if(nums[right]!=0){inttem=nums[left];nums[left]=nums[right];nums[right]=tem;left++;}right++;}}}

11. 盛最多水的容器

11. 盛最多水的容器

双指针

如果短的边界不变，不管长的边界怎么向内移动，容积只会变小

所以每次要移动短的边界每次将

对应的数字较小的那个指针往另一个指针的方向移动一个位置，就表示我们认为这个指针不可能再作为容器的边界了

classSolution{publicintmaxArea(int[]height){intl=0,r=height.length-1;intans=0;while(l<r){inttem=Math.min(height[l],height[r])*(r-l);ans=Math.max(ans,tem);if(height[l]<=height[r])l++;elser--;}returnans;}}

167. 两数之和 II - 输入有序数组

167. 两数之和 II - 输入有序数组

双指针

sum过大则最大数不选，于是right--

sum过小则最小数不选，于是left++

classSolution{publicint[]twoSum(int[]numbers,inttarget){intleft=0,right=numbers.length-1;while(left<right){intsum=numbers[left]+numbers[right];if(sum==target){returnnewint[]{left+1,right+1};}if(sum>target){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{publicList<List<Integer>>threeSum(int[]nums){Arrays.sort(nums);//先排序成有序的List<List<Integer>>ans=newArrayList<>();intn=nums.length;for(inti=0;i<n-2;i++){if(i>0&&nums[i]==nums[i-1]){//nums[i]去重，遇到重复直接跳过continue;}if(nums[i]+nums[i+1]+nums[i+2]>0)break;//优化一if(nums[i]+nums[n-1]+nums[n-2]<0)continue;//优化二intj=i+1,k=n-1;while(j<k){intsum=nums[i]+nums[j]+nums[k];if(sum<0){j++;}elseif(sum>0){k--;}else{ans.add(List.of(nums[i],nums[j],nums[k]));j++;while(j<k&&nums[j]==nums[j-1]){//nums[j]去重j++;}k--;while(k>j&&nums[k]==nums[k+1]){//nums[k]去重k--;}}}}returnans;}}

优化：

1. 如果当前最小的三个数相加都大于0，即nums[i] + nums[i + 1] + nums[i + 2] > 0，则说明后面的数不可能存在符合题目的，直接break
2. 如果当前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){intn=height.length;int[]q=newint[n];int[]h=newint[n];q[0]=height[0];h[n-1]=height[n-1];for(inti=1;i<n;i++){q[i]=Math.max(q[i-1],height[i]);}for(inti=n-2;i>=0;i--){h[i]=Math.max(h[i+1],height[i]);}intans=0;for(inti=0;i<n-1;i++){ans+=Math.min(q[i],h[i])-height[i];}returnans;}}

时间复杂度O(n)

空间复杂度O(n)

相向双指针

优化一下空间复杂度

原理类似11. 盛最多水的容器

classSolution{publicinttrap(int[]height){intn=height.length;intans=0;intleft=0;intright=n-1;intpreMax=0;// 前缀最大值，随着左指针 left 的移动而更新intsufMax=0;// 后缀最大值，随着右指针 right 的移动而更新while(left<right){preMax=Math.max(preMax,height[left]);sufMax=Math.max(sufMax,height[right]);if(preMax<sufMax){ans+=preMax-height[left];left++;}else{ans+=sufMax-height[right];right--;}}returnans;}}

总结

双指针（Two Pointers）：

通过维护两个指针的位置，让两个指针按照某种规则移动，从而减少不必要的遍历。

传统暴力：

fori:forj:判断

时间复杂度：O(n²)

双指针：

left → ← right

两个指针共同移动，时间复杂度：O(n)

核心：不需要回头，通过指针移动缩小问题范围