当前位置：首页 > article >正文

Hot100算法刷题：双指针

article 2025/3/16 2:11:25

双指针

盛水最多的容器

在这里插入图片描述

思路

计算出宽（索引相减）、高（取短板小的那个，min），设置全局变量是最大的体积，和当前的体积。

暴力求解，两个for循环遍历，第一层固定住长方形的左边，第二层控制长方形的右边。依次计算每一步的体积，然后更新最大体积的值。

注意：长方形左边取值：0~len-1，右边取值：1-len；

但报错：超出时间限制。

观察到2 <= n <= 10(5)，说明线比较多。所以暴力求解不行。要优化算法。下面使用另外一个中双指针的方式实现：

考虑使用双指针法来解决，具体思路如下：

初始化两个指针，一个指向数组的开头，一个指向数组的结尾。
计算当前两个指针所指位置形成的容器的面积，并更新最大面积。
移动指向高度较小的指针，因为移动指向高度较大的指针不会使容器的面积增大。
重复上述步骤，直到两个指针相遇。

代码如下：

class Solution {
public:
    int maxArea(vector<int>& height) {
        int left = 0;
        int right = height.size() - 1;
        int maxV = 0;

        while (left < right) {
            // 计算当前容器的面积
            int area = min(height[left], height[right]) * (right - left);
            // 更新最大面积
            maxV = max(maxV, area);

            // 移动指向高度较小的指针
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }

        return maxV;
    }
};

链表里是否有环？快慢指针Floyd判圈法

核心思路：快指针走2步，慢指针走1步，如果存在环，那么必定快指针追上慢指针。如果不存在环，快指针先到达链表末尾。循环条件：快指针不为空，且下一个不为空

进阶版：返回这个环节点的位置。不仅判断有咩有，还要知道在哪里

思路：分2阶段：判断有环，找环位置。找环位置有一个定理：当快慢指针相遇时，我们可以证明从链表头节点和相遇点同时出发，以相同的速度移动，最终会在环的入口节点相遇。

合并两个有序链表

三数之和

排序、双指针、遍历去重复

对数组升序，方便跳过重复的元素，用双指针两头夹闭，优化查找。

sort( nums.begin(), nums.end() )

遍历数组，i指针就作为3元组第一个元素。l、r指针指向第2个，和最后一个。根据和的情况，移动左右指针，和大于0，那么当前和太大，需要r左移，减少正数。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        //排序数组
        sort( nums.begin(), nums.end() );
        //应该初始化为空向量；
        vector<vector<int>> threearray;

        //遍历数组，根据sum和0的大小，移动左右指针。sum不为0则已知移动，直到为0，就加入和为0的三元组。
        for(int i=0; i<nums.size()-2; i++ ){
            //跳出极端情况，如果一开始左边都>0,则无解！
            if(nums[i] > 0)     break;

            //跳过重复元素,根据i的情况跳过
            if(i>0 && nums[i-1] == nums[i]) continue;
            //需要把l、r指针写到循环里面，因为每次对于新的i，都要从新找所有可能情况！！
            //left初始化应该为i+1！！！
            int left=i+1;
            int right=nums.size()-1;

            //双指针的遍历全部条件是：  left < right
            while( left < right ){
                int sum = nums[i] + nums[left] + nums[right]; 
                if( sum > 0 ){
                    right--;
                }   
                else if( sum < 0 ){
                    left++;
                }
                else{
                    //找到了一个满足条件的三元组，使用push_back()函数，在向量中添加元组。
                    threearray.push_back({nums[i], nums[left], nums[right]});
                    //跳过l、r指针的重复元素的指针移动
                    while(left<right && nums[left] == nums[left+1]) {
                        left++;
                    }
                    while(left<right && nums[right] == nums[right-1]){
                        right--;
                    }

                    //这是加入元组后，while循环一次的指针移动
                    left++; right--;
                }  
            }
            
        }
        return threearray;

    }
};

实现时候需要注意的点

threearray 初始化问题：使用push_back函数吧元组加入二维向量中，那初始化时应该初始化空向量
left 指针初始化问题
找到满足条件的三元组后指针移动问题

二叉树

二叉树直径

思想

使用深度优先搜索（DFS）解决，先通过递归函数计算以每个节点为根的子树最大深度，同时计算经过该节点的最长路径长度。

计算最大深度，然后计算更新全局变量直径diameter表示当前找到的最长路径长度。经过当前节点的最长路径长度=左子树最大深度+右子树最大深度,具体思路如下：

定义递归函数：定义一个递归函数来计算以每个节点为根的子树的最大深度。在计算最大深度的过程中，我们可以同时计算经过该节点的最长路径长度。
计算最大深度：对于每个节点，其最大深度等于其左子树的最大深度加上右子树的最大深度再加上 1（当前节点）。
计算直径：在计算每个节点的最大深度时，我们可以更新全局变量diameter，diameter表示当前找到的最长路径长度。经过当前节点的最长路径长度等于其左子树的最大深度加上右子树的最大深度。
返回结果：最终返回diameter。

class Solution {
public:
    int diameter=0;

    int depth(TreeNode* root){
        if( root==nullptr)  return 0;
        int leftDepth = depth(root->left);
        int rightDepth = depth(root->right);

        //经过当前节点的最大直径 = 当前节点的左子树深度+右子树深度
        diameter = max(diameter, leftDepth + rightDepth);

        //返回树的深度
        return max(leftDepth, rightDepth) + 1;
    }

    

    int diameterOfBinaryTree(TreeNode* root) {
        depth(root);
        return diameter;
    }
};