一、背景知识
- 双指针（Two Pointers）：指的是在遍历元素的过程中，不是使用单个指针进行访问，而是使用两个指针进行访问，从而达到相应的目的。
- 对撞时针：
- 两个指针方向相反
- 对撞指针一般用来解决有序数组或者字符串问题
- 快慢指针：
- 两个指针方向相同，速度不同。移动快的指针被称为 「快指针（fast）」，移动慢的指针被称为「慢指针（slow）」
- 快慢指针一般用于处理数组中的移动、删除元素问题，或者链表中的判断是否有环、长度问题。
- 分离双指针：
- 两个指针分别属于不同的数组 / 链表
- 分离双指针一般用于处理有序数组合并，求交集、并集问题。
滑动窗口法：
两个指针，一前一后组成滑动窗口，并计算滑动窗口中的元素的问题。一般是右端向右扩充，达到停止条件后右端不动，左端向右端逼近，逼近达到停止条件后，左端不动，右端继续扩充。
- 滑动窗口法一般用于处理字符串匹配问题和子数组问题
- 时间复杂度
二、例题
总结：
- 要移动多个指针的情况可以分解成双指针的情况（1+n）
- 关键是什么条件下移动哪个指针，分开思考，一起走就容易乱
1、移动零（快慢指针）
突破点：右指针是贴着左指针开始往右移的，不是从数组右端往左移，因为那样会搅乱数组元素的相对顺序
class Solution {
public void moveZeroes(int[] nums) {
int l=0;//左指针
int r=0;//右指针
int count=0;//计算0的个数
while(r<nums.length){
if(nums[r]!=0 && nums[l]==0){//找到0，交换后，左右指针都往右移
nums[l]=nums[r];
nums[r]=0;
count++;
l++;
}
if(nums[l]!=0){//没找到0，左右指针都往右移
l++;
}
//前两种情况都有r++; 所以把它提到外面，大家都能用
r++;//如果只有左指针找到0，右指针继续往右移
}
}
}
代码优化：封装方法
class Solution {
public void moveZeroes(int[] nums) {
int n = nums.length, left = 0, right = 0;
while (right < n) {
if (nums[right] != 0) {
swap(nums, left, right);
left++;
}
right++;
}
}
public void swap(int[] nums, int left, int right) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
}
}
2、盛最多水的容器（对撞指针）
突破点：不是同时移动两个指针，而是只移动较小的那个，因为较小的值改变会影响整体面积
public class Solution {
public int maxArea(int[] height) {
int l = 0, r = height.length - 1;//左右指针分别指向数组的头尾
int ans = 0;//维护一个最大值
while (l < r) {
int area = Math.min(height[l], height[r]) * (r - l);//当前面积，不一定是最大值
ans = Math.max(ans, area);
//移动数字较小的那个指针，整体面积才会发生变化
if (height[l] <= height[r]) {
++l;
}
else {
--r;
}
}
return ans;
}
}
3、三数之和（对撞指针）
突破点：三个指针的相对方位不会改变，一左一中一右，
它们也不会走对方走过的路，因为它们三个实际上是相同的
如果改变了方位，就会出现重复的三元组
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
int n = nums.length;
Arrays.sort(nums);
List<List<Integer>> ans = new ArrayList<List<Integer>>();
// 枚举 a
for (int first = 0; first < n; ++first) {
// 需要和上一次枚举的数不相同
if (first > 0 && nums[first] == nums[first - 1]) {
continue;
}
// c 对应的指针初始指向数组的最右端
int third = n - 1;
int target = -nums[first];
// 枚举 b
for (int second = first + 1; second < n; ++second) {
// 需要和上一次枚举的数不相同
if (second > first + 1 && nums[second] == nums[second - 1]) {
continue;
}
// 需要保证 b 的指针在 c 的指针的左侧
// 因为当b走到c的右边时，相当于原来的c，会有重复的三元组产生
while (second < third && nums[second] + nums[third] > target) {
//b和c之和大于target，b是往右走值是增大的，所以要移动c指针往左走
--third;
}
// 如果指针重合，随着 b 后续的增加
// 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
if (second == third) {
break;
}
//找到了
if (nums[second] + nums[third] == target) {
List<Integer> list = new ArrayList<Integer>();
list.add(nums[first]);
list.add(nums[second]);
list.add(nums[third]);
ans.add(list);
}
}
}
return ans;
}
}
4、接雨水（对撞指针）
突破点：是从两边向中间逼近，而非从左到右
class Solution {
public int trap(int[] height) {
int ans=0;
int left=0,right=height.length-1;//左右指针分别指向数组的头尾端
int leftMax=0,rightMax=0;
while(left<right){//指针未相撞
leftMax=Math.max(leftMax,height[left]);
rightMax=Math.max(rightMax,height[right]);
if(height[left]<height[right]){
ans+=leftMax-height[left];//当前height[left]夹在leftMax和rightMax中间，所以它的存水量受制于最小值
++left;//移动最小值，才会改变可存水量
}else{
ans+=rightMax-height[right];
--right;
}
}
}
}
