【算法题】从0培养算法思想——双指针篇
【算法题】从0培养算法思想——双指针篇
在这个专栏里我会收集一些很经典的算法题，并分享算法原理和题解，这里面每一道题或者带给了我新的思路，或者是代码简洁高效，或者题目在面试中出现的频率很高。我想把它们记录下来，大家有更好的思路也欢迎大家在评论区交流啊！ 欢迎大家交流！！！ 欢迎大家交流！！！ 欢迎大家交流！！！
双指针
常⻅的双指针有两种形式，⼀种是对撞指针，⼀种是左右指针。
对撞指针：⼀般⽤于顺序结构中，也称左右指针。
• 对撞指针从两端向中间移动。⼀个指针从最左端开始，另⼀个从最右端开始，然后逐渐往中间逼
近。
• 对撞指针的终⽌条件⼀般是两个指针相遇或者错开（也可能在循环内部找到结果直接跳出循
环），也就是：
◦ left == right （两个指针指向同⼀个位置）
◦ left > right （两个指针错开）
快慢指针：⼜称为⻳兔赛跑算法，其基本思想就是使⽤两个移动速度不同的指针在数组或链表等序列结构上移动。
这种⽅法对于处理环形链表或数组⾮常有⽤。
其实不单单是环形链表或者是数组，如果我们要研究的问题出现循环往复的情况时，均可考虑使⽤快
慢指针的思想。
快慢指针的实现⽅式有很多种，最常⽤的⼀种就是：
• 在⼀次循环中，每次让慢的指针向后移动⼀位，⽽快的指针往后移动两位，实现⼀快⼀慢。
1.移动零问题
题目链接：
https://leetcode.cn/problems/move-zeroes/description/
解题思路：
利用两个指针将数组分为三区间，分别是不含零元素的区间，全是零元素的区间，未扫描的区间。
代码实现：
class Solution {
public void moveZeroes(int[] nums) {
int right=0,left=0;
int length=nums.length;
while(right<length){
if(nums[right]!=0){
int tmp=nums[right];
nums[right]=nums[left];
nums[left]=tmp;
left++;
}
right++;
}
}
}2. 称最多水的容器
题目链接：
解题思路：
设两个指针 left ， right 分别指向容器的左右两个端点，此时容器的容积 ：
v = (right - left) * min( height[right], height[left])
容器的左边界为 height[left] ，右边界为 height[right] 。
为了⽅便叙述，我们假设「左边边界」⼩于「右边边界」。
如果此时我们固定⼀个边界，改变另⼀个边界，⽔的容积会有如下变化形式：
- 容器的宽度⼀定变⼩。
- 由于左边界较⼩，决定了⽔的⾼度。如果改变左边界，新的⽔⾯⾼度不确定，但是⼀定不会超过右边的柱⼦⾼度，因此容器的容积可能会增⼤。
- 如果改变右边界，⽆论右边界移动到哪⾥，新的⽔⾯的⾼度⼀定不会超过左边界，也就是不会超过现在的⽔⾯⾼度，但是由于容器的宽度减⼩，因此容器的容积⼀定会变⼩的。
由此可⻅，左边界和其余边界的组合情况都可以舍去。所以我们可以 left++ 跳过这个边界，继
续去判断下⼀个左右边界。
当我们不断重复上述过程，每次都可以舍去⼤量不必要的枚举过程，直到 left 与 right 相
遇。期间产⽣的所有的容积⾥⾯的最⼤值，就是最终答案。
代码实现：
class Solution {
public int maxArea(int[] height) {
int length=height.length;
int left=0;
int right=length-1;
int max=0;
int v=0;
while(left!=right){
if(height[left]<=height[right]){
v=(right-left)*height[left];
if(v>max){
max=v;
}
left++;
}else{
v=(right-left)*height[right];
if(v>max){
max=v;
}
right--;
}
}
return max;
}
}3.三数之和
题目链接：
解题思路：
本题与两数之和类似，是⾮常经典的⾯试题。
与两数之和稍微不同的是，题⽬中要求找到所有「不重复」的三元组。那我们可以利⽤在两数之和
那⾥⽤的双指针思想，来对我们的暴⼒枚举做优化：
- 先排序；
- 然后固定⼀个数 a ：
- 在这个数后⾯的区间内，使⽤「双指针算法」快速找到两个数之和等于 -a 即可。
但是要注意的是，这道题⾥⾯需要有「去重」操作
- 找到⼀个结果之后， left 和 right 指针要「跳过重复」的元素；
- 当使⽤完⼀次双指针算法之后，固定的 a 也要「跳过重复」的元素。
代码实现：
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
int length=nums.length;
List<List<Integer>> list=new ArrayList<>();
for(int i=0;i<length;){
if(nums[i]>0){
return list;
}
int right=length-1;
int left=i+1;
int count=-nums[i];
while(left<right){
if(nums[left]+nums[right]==count){
list.add(new ArrayList<Integer>(Arrays.asList(nums[i],nums[left],nums[right])));
right--;
left++;
while(left<right&&nums[right]==nums[right+1]){
right--;
}
while(left<right&&nums[left]==nums[left-1]){
left++;
}
}else if(nums[left]+nums[right]<count){
left++;
}else{
right--;
}
}
i++;
while(i<length&&nums[i]==nums[i-1]){
i++;
}
}
return list;
}
}