双指针CSP-J

💡 核心思想

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

🎯 直觉理解

想象你在一排人里找两个人，他们的身高之和恰好等于 180cm。如果人是随机站的，你得两两配对试——$O(n^2)$。但如果人按身高从矮到高站好，你让最矮和最高先配，和太小就让矮的那个换高一点的，和太大就让高的换矮一点的——两个指针各走一遍就够了，$O(n)$。

📝 算法流程

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

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

📊 复杂度分析

💻 参考实现（C++）

#include <bits/stdc++.h>
using namespace std;
// 对撞指针：有序数组中找两数之和等于 target
int main() {
    int n, target; cin >> n >> target;
    vector<int> 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;
}

⚠️ 常见坑点

📚 相关题目