双指针算法（超详细版）

用户11445909

发布于 2025-01-13 20:34:50

13300

代码可运行

文章被收录于专栏：猫咪-9527猫咪-9527

运行总次数：0

代码可运行

1. 双指针

双指针是一种高效解决问题的算法思想，主要分为以下两类：

快慢双指针
对撞双指针

1.1 快慢双指针

1.1.1 循环链表检测（141. 环形链表）

解题思路：

定义快指针 fast 和慢指针 slow，均从链表头部开始。
快指针每次走两步，慢指针每次走一步。
如果快指针和慢指针在某一时刻相遇，则链表存在环；如果快指针到达链表尾部（即 fast == nullptr），则链表无环。

C++ 实现：

class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode *slow = head, *fast = head; // 初始化快慢指针
        while (fast && fast->next) { // 快指针和其下一节点不为空
            slow = slow->next; // 慢指针走一步
            fast = fast->next->next; // 快指针走两步
            if (fast == slow) // 相遇，说明有环
                return true;
        }
        return false; // 快指针走到链表末尾，无环
    }
};

C 语言实现：

typedef struct ListNode ListNode;
bool hasCycle(struct ListNode *head) {
    ListNode *slow = head, *fast = head; // 初始化快慢指针
    while (fast && fast->next) { // 快指针和其下一节点不为空
        slow = slow->next; // 慢指针走一步
        fast = fast->next->next; // 快指针走两步
        if (fast == slow) // 相遇，说明有环
            return true;
    }
    return false; // 快指针走到链表末尾，无环
}

1.1.2 中间节点查找（876. 链表的中间结点）

解题思路：

定义快指针 fast 和慢指针 slow，均从链表头部开始。
快指针每次走两步，慢指针每次走一步。
当快指针到达链表尾部时，慢指针指向链表的中间节点。

C++ 实现：

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode *slow = head, *fast = head; // 初始化快慢指针
        while (fast && fast->next) { // 快指针和其下一节点不为空
            slow = slow->next; // 慢指针走一步
            fast = fast->next->next; // 快指针走两步
        }
        return slow; // 返回中间节点
    }
};

C 语言实现：

typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {
    ListNode *slow = head, *fast = head; // 初始化快慢指针
    while (fast && fast->next) { // 快指针和其下一节点不为空
        slow = slow->next; // 慢指针走一步
        fast = fast->next->next; // 快指针走两步
    }
    return slow; // 返回中间节点
}

1.2 对撞指针

1.2.1 双变化趋势对撞指针（11. 盛最多水的容器）

解题思路：

定义左右指针 left 和 right，分别指向数组的最左端和最右端。
容器的宽度为 right - left，高度由两指针指向的值中较小的决定，即 min(height[left], height[right])。
容积计算公式：v = (right - left) * min(height[left], height[right])。
每次比较两指针的高度，移动较小高度的指针，以寻找更大的容积。

注意：

每次移动指针，容器宽度减小。
当容器高度发生变化时，容积才可能增大。

C++ 实现：

class Solution {
public:
    int maxArea(vector<int>& height) {
        int left = 0, right = height.size() - 1, ret = 0; // 初始化指针和结果
        while (left < right) { // 指针未相遇
            int v = min(height[left], height[right]) * (right - left); // 容积
            ret = max(ret, v); // 更新最大容积
            if (height[left] < height[right]) // 移动较小高度的指针
                left++;
            else
                right--;
        }
        return ret;
    }
};

C 语言实现：

#define MIN(a, b) ((b) < (a) ? (b) : (a))
#define MAX(a, b) ((b) > (a) ? (b) : (a))

int maxArea(int* height, int heightSize) {
    int ans = 0, left = 0, right = heightSize - 1; // 初始化指针和结果
    while (left < right) { // 指针未相遇
        int area = (right - left) * MIN(height[left], height[right]); // 容积
        ans = MAX(ans, area); // 更新最大容积
        if (height[left] < height[right]) // 移动较小高度的指针
            left++;
        else
            right--;
    }
    return ans;
}

1.2.2 单变化趋势对撞指针（611. 有效三角形的个数）

解题思路：

如果 nums[i] + nums[left] > nums[right]，则可以组成三角形。
让 left 不断接近 i，逐步找到所有满足条件的组合。

C++ 实现：

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end()); // 数组排序
        int ret = 0, n = nums.size();
        for (int right = n - 1; right >= 2; right--) { // 固定最长边
            int left = 0, i = right - 1; // 初始化左右指针
            while (left < i) { // 左右指针未相遇
                if (nums[i] + nums[left] > nums[right]) { // 满足三角形条件
                    ret += i - left; // 统计可以组成三角形的数量
                    i--; // 缩小右边
                } else {
                    left++; // 增大左边
                }
            }
        }
        return ret;
    }
};