算法——双指针

- 日理万妓 2024-02-18 13:03 177阅读 0赞

## 一、背景知识 ##

>  *  双指针（Two Pointers）：指的是在遍历元素的过程中，不是使用单个指针进行访问，而是使用两个指针进行访问，从而达到相应的目的。
>  *  **对撞时针**：
>     
>      *  两个指针方向相反
>      *  对撞指针一般用来解决有序数组或者字符串问题
>  *  快慢指针：
>     
>      *  两个指针方向相同，速度不同。移动快的指针被称为 「快指针（fast）」，移动慢的指针被称为「慢指针（slow）」
>      *  快慢指针一般用于处理数组中的移动、删除元素问题，或者链表中的判断是否有环、长度问题。
>  *  分离双指针：
>     
>      *  两个指针分别属于不同的数组 / 链表
>      *  分离双指针一般用于处理有序数组合并，求交集、并集问题。
>  *  滑动窗口法：
>     
>      *  两个指针，一前一后组成滑动窗口，并计算滑动窗口中的元素的问题。一般是右端向右扩充，达到停止条件后右端不动，左端向右端逼近，逼近达到停止条件后，左端不动，右端继续扩充。
>      *  滑动窗口法一般用于处理字符串匹配问题和子数组问题
>  *  时间复杂度![O(n)][O_n]

## 二、例题 ##

> 总结：
> 
>  *  要移动多个指针的情况可以分解成双指针的情况（1+n）
>  *  关键是什么条件下移动哪个指针，分开思考，一起走就容易乱

### 1、移动零（快慢指针） ###

### ![8afadb98a6ff4368b6064f84eb209a6c.png][] ###

> 突破点：右指针是贴着左指针开始往右移的，不是从数组右端往左移，因为那样会搅乱数组元素的相对顺序

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，右指针继续往右移
            }
        }
    }

![d9e3b7183967402abb7bb1e8fab421e7.jpeg][]

![7ad5f2dc92aa4864b054e314a05add0b.png][]

代码优化：封装方法

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、盛最多水的容器（对撞指针） ###

![c8f3cdefdbaf4265adbf14ce7b69d206.png][]

![01289209f3774836a78b1e29afd9e90e.png][]

> 突破点：不是同时移动两个指针，而是只移动较小的那个，因为较小的值改变会影响整体面积

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;
        }
    }

![b8f55ad176854faf901d8755d2e1c9b9.jpeg][]

### 3、三数之和（对撞指针） ###

![8fb99e6c13a8453684e57215bd03615b.png][]

![c494a921d25549659d151614ea6449f0.png][]

> 突破点：三个指针的相对方位不会改变，一左一中一右，  
> 它们也不会走对方走过的路，因为它们三个实际上是相同的  
> 如果改变了方位，就会出现重复的三元组

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;
        }
    }

![fb592bd2cc0a4153b193576f002dc514.jpeg][]

### 4、接雨水（对撞指针） ###

![cba1115291a0430f8cca1dafd36f2991.png][]

![35b42b264bab48b1b7cad93cd29dfbba.png][]

> 突破点：是从两边向中间逼近，而非从左到右

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;
                }
            }
        }
    }

![916a7d15b9f840c58fbbba2539423ea9.jpeg][]

[O_n]: https://latex.csdn.net/eq?O%28n%29
[8afadb98a6ff4368b6064f84eb209a6c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/18/71a142b09e97438eb2ad95ec08f6daa3.png
[d9e3b7183967402abb7bb1e8fab421e7.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/18/6b82d487eb53459395ce00b213af15ba.png
[7ad5f2dc92aa4864b054e314a05add0b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/18/8456da18d5d4483687885fe15eae330c.png
[c8f3cdefdbaf4265adbf14ce7b69d206.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/18/9f735917069a4cfb8bf00693e478db7c.png
[01289209f3774836a78b1e29afd9e90e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/18/46199f2e165a4995a6f5cfed30ba80bc.png
[b8f55ad176854faf901d8755d2e1c9b9.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/18/f7af9726f3234e1c8d167a5db269c307.png
[8fb99e6c13a8453684e57215bd03615b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/18/112c0843a18648029ddb43bb34e66ed7.png
[c494a921d25549659d151614ea6449f0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/18/b1184e03d83044a2b84b9e25ceb5eedd.png
[fb592bd2cc0a4153b193576f002dc514.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/18/a7a999c337654c1884848f33c4f67b85.png
[cba1115291a0430f8cca1dafd36f2991.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/18/3d56102c0daf4484af9ed261cb8d1aa0.png
[35b42b264bab48b1b7cad93cd29dfbba.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/18/74c0890e5f3e475c8f0b210aa5c0eccf.png
[916a7d15b9f840c58fbbba2539423ea9.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/18/faffc909993b498286890e368f68290f.png