LeeCode Hot100 之双指针篇

最新推荐文章于 2025-06-01 11:36:00 发布

Arth_u_r

最新推荐文章于 2025-06-01 11:36:00 发布

阅读量1.6k

点赞数 20

分类专栏： LeeCode LeeCodeHot100 文章标签：算法数据结构 leetcode 左右指针快慢指针双指针

本文链接：https://blog.csdn.net/Arth_u_r/article/details/147234701

版权

LeeCode 同时被 2 个专栏收录

2 篇文章

订阅专栏

LeeCodeHot100

2 篇文章

订阅专栏

1.双指针的简述

1.1 双指针的定义

双指针（Two Pointers） 是一种常用的算法技巧，通常用于 数组、链表或字符串 等线性结构的问题中。它的核心思想是 使用两个指针（索引或引用）在数据结构中协同遍历或比较元素，从而高效地解决问题。

1.2双指针的类型及适合的题型

1.2.1 左右指针（对撞指针）

其特点是一个指针从左端（left）开始，另一个从右端（right）开始。根据条件向中间移动，直到 left 和 right 相遇。

其适用于有序数组，两数之和，反转数组等方面的题型。其中经典排序方法中，快速排序就有左右指针的影子。

1.2.1 快慢指针（前后指针）

其特点是两个指针从同一起点（也可以不同点出发，但是移动方向相同）出发，但移动速度不同（如 fast 每次走 2 步，slow 每次走 1 步）。

其应用的经典问题就是判断链表中是否有环，找链表中点（快指针移动两步，慢指针移动一步）、删除重复元素（将数组排序，然后根据情况移动快慢指针。）等等。

快慢指针还有一个特殊的应用就是快慢指针中间囊括的区域就是一个窗口，因此滑动窗口可以说也是快慢指针的变形。

2.算法题详解

2.1移动零

如果没有要保持非零元素的顺序相对不变的条件，那这题将会变的更简单。直接使用左右指针，将左边的0元素和右边的非零元素对调即可，当两个指针相遇的时候结束。这也是我一开始没有仔细审题，读完题就直接想到了这个方法，结果写完发现是错的😂。

那么既然要维持非零元素的顺序不变，就应该将0与离它最近的非零元素交换位置，这样将0元素一点一点的往后移动，直到最后所有的零元素都在最后面即可。依据“应该将0与离它最近的非零元素交换位置”这一条，就不难想到这是一个快慢指针类型的题目。

按照这样的思路，那么一个指针left就在找0元素，另一个指针right就快速向后找非0元素。因此right找到的非零元素与left找到的零元素会交换位置，也就是说left指针之前的元素均为非0元素。left的作用维护非零元素的数组，而right的作用快速遍历找到后续的非0元素。那么有没有更简单的方法？其实，无论left指针所指向的元素是不是0，只要把后面当right遍历到的非0元素都和left的元素交换位置，就可以满足left维护的是非零元素的数组。而当right遍历完整个数组的时候，就说明right已经找遍了所有的非零元素，此时就可以结束了。

 void moveZeroes(vector<int>& nums) {
        int left =0;        // 维护非0元素的队列
        int right = 0;      // 向后查找0元素
        int len = nums.size();
        while(right <len){
            while()
            if(nums[right] != 0){
                swap(nums[left],nums[right]);
                left++;
            }
            right++;
        }
    }

2.2盛最多的雨水

水的容量和什么有关？1.柱子的高度（而且与短边有关）；2.柱子见的距离。套用两种指针方法，第一快慢指针法，显然不好，因为既要维护柱子的高度，又要不断的维护两个指针间的距离来不断的缩小或者放大距离。

既然找最大的容量，那么当然是期望柱子间的距离越宽越好，柱子的高度越长越好。那么，干脆就直接将柱子间的宽度设置为最大（即左右指针）。计算当前的容量，然后不断移动当前较短的柱子，期望在此能找到更高的柱子，使得容量进一步增大。按照这个思路就有了以下的代码：

  int maxArea(vector<int>& height) {
    // 利用左右指针
    // 因为雨水的面积主要依赖于两根柱子间的距离，以及较短柱子的高度，那么可以先将两个柱子见的距离移动到最大，然后依次减小。每次减小的依据是移动较短的柱子，期望找到更大的柱子。
    int left = 0;
    int right = height.size()-1;
    int max_V = 0;
    while(left<right){
        int tempV = 0;
        tempV = (min(height[left],height[right]) * (right -left));
        max_V = max(max_V,tempV);
        height[left]<height[right]?left++:right--;
    }
    return max_V;
    }

2.3三数之和

找三个元素怎么用双指针？？？

那么，是否可以将三元解降低为两元？一个初步的思路就是，顺序遍历数组中的每一个元素，然后在数组后续元素中（为什么不找前面的元素了？因为遍历前面的元素的时候，就已经找过了）寻找是否存在其他两个元素的和，为这个元素的相反数？

因此，问题就被拆分成了，如何在数组中找到两个元素的和为一特定元素的问题，第一种方法就可以参考hot100之哈希表篇的例题两数之和（LeeCode Hot 100之哈希表篇-CSDN博客）。

第二种方法就是利用双指针，而左右指针是寻找两数之和的典型方法。对于一个排序好的数组来说，利用左右指针遍历找两数之和，如果nums[left] + nums[right] < target 则 left++；反之，若nums[left] + nums[right] > target 则 right--;nums[left] + nums[right] = target则进行对应操作即可。

 vector<vector<int>> twoSum(vector<int>& nums,int left,int right,int target,int value){
        vector<vector<int>> answer;
        while(left<right){
            if( nums[right] + nums[left] == target){
               vector<int> res;
               res.emplace_back(value);
               res.emplace_back(nums[left]);
               res.emplace_back(nums[right]);
               answer.push_back(res);
               //跳过重复元素
               while(left < right && nums[left] == nums[left+1]) left++;
               left++;
               right--;
            }else if(nums[right] + nums[left] < target){
                left++;
            }else{
                right--;
            }
        }
        return answer;
    }
    vector<vector<int>> threeSum(vector<int>& nums) {
        // 三数和的问题降低难度为两数和
        // 对于每一个元素，后面数组中是否存在两个元素的和 是他的相反数？
        int len = nums.size();
        vector<vector<int>> answer;
        sort(nums.begin(),nums.end());
        for(int i = 0; i<len;i++){
            // 且跳过重复值
            if(i>0 && nums[i] == nums[i-1])
                continue;
            int target = nums[i];
            auto results = twoSum(nums,i+1,len-1,-target,target);
            answer.insert(answer.end(),results.begin(),results.end());
        }
        return answer;
    }

2.4接雨水

据说缩写和百度一样的某独角兽大厂特别喜欢考这道题目，这道题目看过的都会做，没看过的想要当场手撕出来还是相当不易啊。感觉也是第二题的变形。

感觉带一点动态规划和分治的思想，既然求整个区域的雨水不好求，那就可以把每一单位长度能接的雨水算出来，然后加和就解决啦！

那么每一单位能解多少雨水呢？是不是和该单位左边的柱子有多高以及右边的柱子有多高有关？能接的高度就是max_left_height 和 max_right_height中较短的一条边有关？当然还得减去当前单位自身的高度。由height[5]为例，该单位能接的高度就是min(max_left=2,max_right=3) - height[5](height[5]=0)。

因此只要得到每个单位的左侧最高高度和右侧最高高度就可以啦！其实这就是最简单的左右指针，一个向后遍历，一个向前遍历。结束的条件不是两个指针相撞，而是各自遍历完整个数组（就是最简单的顺序遍历）。然后再计算每个单位的雨水量即可。代码如下：

 int trap(vector<int>& height) {
        int n = height.size();
        vector<int> left_max;    //记录每个位置 左边最高的高度
        left_max.reserve(n);
        vector<int> right_max;   // 记录每个位置右边最高的高度
        right_max.reserve(n);
        // 遍历获取每个位置的右边最高高度
        // 从左往右计算 left_max
        left_max[0] = height[0];
        for (int i = 1; i < n; i++) {
            left_max[i] = max(left_max[i - 1], height[i]);
        }

        // 从右往左计算 right_max
        right_max[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            right_max[i] = max(right_max[i + 1], height[i]);
        }
        // 对于每个位置来说 这个单位可以接的雨水 vi = [min(left_max_i,right_max_i)- height[i]]
        int V =0;
        for(int i =0;i<n;i++){
            int vi = min(right_max[i],left_max[i])-height[i];
            if(vi > 0){
                V+= vi;
            }
        }
        return V;
    }