双指针

概念讲解

什么是双指针？

双指针是使用两个指针来解决问题的技巧，通常可以将 O(n²) 优化到 O(n)。

常见类型

类型 说明 应用
对撞指针 两端向中间移动 两数之和
快慢指针 速度不同 链表环检测
滑动窗口 维护窗口 子数组问题

对撞指针

123456789101112int left = 0, right = n - 1;
while (left < right) {
    if (满足条件) {
        // 处理
        left++;
        right--;
    } else if (需要增大) {
        left++;
    } else {
        right--;
    }
}

滑动窗口

123456789101112int left = 0;
for (int right = 0; right < n; right++) {
    // 扩大窗口
    window.add(nums[right]);
    
    while (窗口需要收缩) {
        window.remove(nums[left]);
        left++;
    }
    
    // 更新答案
}

考点分析

初赛考查方式

  1. 程序阅读： 双指针程序
  2. 编程题： 双指针应用

常见考点

  • 两数之和
  • 滑动窗口最大值
  • 链表环检测

例题精讲

例题 1：两数之和

题目： 在有序数组中找两个数，使其和等于 target。

解答：

1234567int left = 0, right = n - 1;
while (left < right) {
    int sum = a[left] + a[right];
    if (sum == target) return {left, right};
    else if (sum < target) left++;
    else right--;
}

例题 2：滑动窗口

题目： 求长度为 k 的子数组的最大和。

解答：

1234567int sum = 0, maxSum = 0;
for (int i = 0; i < k; i++) sum += a[i];
maxSum = sum;
for (int i = k; i < n; i++) {
    sum += a[i] - a[i-k];
    maxSum = max(maxSum, sum);
}

练习题

  1. 双指针的时间复杂度是多少？
查看答案

O(n)

每个元素最多被访问一次，两个指针总共移动 n 次。

  1. 滑动窗口的适用场景是什么？
查看答案

滑动窗口适用于：

  • 子数组/子串问题：求满足条件的最长/最短子数组
  • 连续区间问题：求区间和、区间最值
  • 字符串匹配：包含所有字符的最短子串

特点：窗口大小可变或固定，左右边界单调移动。

  1. 如何用快慢指针检测链表环？
查看答案
123456789101112131415bool hasCycle(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;
    
    while (fast && fast->next) {
        slow = slow->next;        // 慢指针走一步
        fast = fast->next->next;  // 快指针走两步
        
        if (slow == fast) {       // 相遇说明有环
            return true;
        }
    }
    
    return false;  // 快指针到末尾，无环
}

易错点

⚠️ 注意：

  1. 对撞指针要求数组有序
  2. 滑动窗口要注意窗口大小
  3. 双指针通常将 O(n²) 优化到 O(n)
  4. 注意指针的移动条件