双指针CSP-J

💡 核心思想

双指针是一种通过两个指针协同移动来优化枚举的技巧。常见形式：对撞指针（两端向中间）、快慢指针（一个快一个慢）、滑动窗口（维护一个动态区间）。通常能将 $O(n^2)$ 优化为 $O(n)$。

🎯 直觉理解

双指针就是两个指针在数组上配合移动，把暴力 $O(n^2)$ 优化成 $O(n)$。典型场景：对撞指针（有序数组找两数之和：一左一右，和大了右指针左移，小了对撞左指针右移）和滑动窗口（维护一段连续区间，右端扩展、左端收缩）。

想想"和为 k 的最短连续子数组"：暴力枚举所有起点终点是 $O(n^2)$；用滑动窗口，右指针不断右移、不满足时左指针右移，每个元素至多进出一次，总时间 $O(n)$。

双指针能用的前提通常是单调性——指针只能单向移动。先问自己"指针能一直往一个方向走吗"，能，双指针就有戏。

📝 算法流程

1. 对撞指针：left=0, right=n-1，根据条件移动 left++ 或 right--
2. 同向指针：维护一个满足条件的窗口，右端扩展、左端收缩
3. 滑动窗口：右指针不断前进，左指针在条件不满足时前进

$$\text{对撞指针每步只需移动一个指针，总移动次数} \le 2n = O(n)$$

📊 复杂度分析

💻 参考实现（C++）

#include 
using namespace std;
// 对撞指针：有序数组中找两数之和等于 target
int main() {
    int n, target; cin >> n >> target;
    vector a(n);
    for (auto& x : a) cin >> x;
    sort(a.begin(), a.end());
    int l = 0, r = n - 1;
    while (l < r) {
        long long sum = (long long)a[l] + a[r];
        if (sum == target) { cout << a[l] << " " << a[r] << endl; return 0; }
        else if (sum < target) l++;
        else r--;
    }
    cout << "No" << endl;
    return 0;
}

⚠️ 常见坑点

📚 相关题目