这道题是 “双指针” 算法的入门必做题，也是考察对 “有序性” 利用能力的经典案例。

---

第一部分：题目描述

题目名称：两数之和 II - 输入有序数组 (Two Sum II)

【题目描述】 给定一个下标从 1 开始的整数序列 $A$，该序列已按照 非递减顺序 排列。 请你从序列中找出两个数，使得它们的和等于给定的目标数 target。 假设每个输入只对应 唯一 的一个答案，而且你 不可以 重复使用相同的元素（即下标不能相同）。 请返回这两个数的下标 index1 和 index2，其中 $1 \le index1 < index2 \le Length$。

注意： 你的解法必须只使用常量级的额外空间，即空间复杂度为 $O(1)$。

【输入格式】 第一行包含两个整数 $n$ 和 $target$，分别表示数组长度和目标和。 第二行包含 $n$ 个整数，表示有序数组 $A$ 的元素，整数之间用空格分隔。

【输出格式】 输出一行，包含两个整数，分别表示满足条件的两个数的下标（下标从 1 开始），中间用空格分隔。

【样例输入 1】

4 9
2 7 11 15

【样例输出 1】

1 2

【样例输入 2】

3 6
2 3 4

【样例输出 2】

1 3

【样例输入 3】

2 -1
-1 0

【样例输出 3】

1 2

【数据范围与提示】

• $2 \le n \le 3 \times 10^4$
• $-1000 \le A[i] \le 1000$
• $-2000 \le target \le 2000$
• 题目保证序列 $A$ 是非递减有序的。
• 题目保证有且仅有一组解。

---

第二部分：教练的解题辅导

1. 预备知识点

在做这道题之前，你需要掌握以下基础：

• 数组/向量 (std::vector) 的基本操作与下标访问。
• 双指针算法 (Two Pointers)：特别是“对撞指针”（左右指针）的思想。
• 单调性/有序性 的理解：知道数组有序意味着什么。
• (可选) 二分查找：虽然不是最优解，但有助于理解为什么能比 $O(n^2)$ 快。

2. 读题关键词分析

很多同学做不出题是因为忽略了题面里的“暗号”。来看这几个词：

• “已按照非递减顺序排列”：这是最重要的提示！看到有序，就要想到二分查找或者双指针。如果用哈希表（Hash Map）做，虽然也能 $O(n)$，但就浪费了这个有序的条件，且空间不是 $O(1)$。
• “下标从 1 开始”：OI 选手的基本功，输出时记得把 0-based 索引转换一下（+1）。
• “空间复杂度 O(1)”：这直接判了哈希表做法的“死刑”。你不能开额外的数组或 Map 来存数。
• “唯一答案”：不用考虑去重，找到一组直接 return 或 break。

3. 启发式思路引导（草稿纸推演）

来，拿出草稿纸，我们模拟一下。

思路一：暴力枚举（老师不推荐，但要懂为什么慢）

• 写两层 for 循环，枚举所有可能的 $i$ 和 $j$。
• 复杂度：$O(n^2)$。
• 评价：在 $n=30000$ 的情况下，$n^2 \approx 9 \times 10^8$，大概率会超时（TLE）。

思路二：二分查找（还可以，但不是最完美的）

• 固定第一个数 $A[i]$，然后在 $i$ 后面的序列里，二分查找 $target - A[i]$。
• 复杂度：$O(n \log n)$。
• 评价：可以通过，利用了有序性，但没有用到极致。

思路三：双指针法（金牌解法） 想象你面前有一排从小到大排好队的数字。我们要找两个数加起来等于 target。

第一步： 我们能不能先拿 最小的数 和 最大的数 加一下试试？

• 左指针 L 指向开头（最小）。
• 右指针 R 指向结尾（最大）。
• 算出 sum = A[L] + A[R]。

第二步： 观察 sum 和 target 的关系（关键推理）：

• 情况 A：sum == target

  • 恭喜！找到了！直接输出 L+1 和 R+1。

• 情况 B：sum > target

  • 推理：现在的和太大了。
  • 我们需要把和变小。
  • 能动 L 吗？A[L] 已经是最小的了，如果把 L 往右移，数只会更大，和也会更大。
  • 所以，必须 把 R 往左移（选一个稍微小一点的大数）。
  • 草稿纸操作：R--。

• 情况 C：sum < target

  • 推理：现在的和太小了。
  • 我们需要把和变大。
  • 能动 R 吗？A[R] 已经是最大的了，如果把 R 往左移，数只会更小。
  • 所以，必须 把 L 往右移（选一个稍微大一点的小数）。
  • 草稿纸操作：L++。

图解演示： 假设数组 [2, 7, 11, 15], target = 9

1. L指向 2，R指向 15。

   • 2 + 15 = 17。
   • 17 > 9 (太大了！)。
   • 既然 2 加上最大的 15 都太大了，那 15 肯定没戏了（因为它跟最小的加都超标）。
   • 决策：抛弃 15，R 左移。

2. L指向 2，R指向 11。

   • 2 + 11 = 13。
   • 13 > 9 (还是大！)。
   • 决策：抛弃 11，R 左移。

3. L指向 2，R指向 7。

   • 2 + 7 = 9。
   • 9 == 9 (中了！)。
   • 输出：1 2 (记得下标+1)。

4. 复杂度分析

• 时间复杂度：

  • 我们的 L 只会往右走，R 只会往左走。
  • 它们最坏的情况就是在中间相遇。
  • 每个元素最多被访问一次。
  • 所以是线性的，$O(n)$。这比二分查找的 $O(n \log n)$ 还要快！

• 空间复杂度：

  • 我们只用了 L, R, sum 这几个变量。
  • 不需要开新数组。
  • 所以是 $O(1)$。完全符合题目要求。

---

第三部分：NOI 风格参考代码 (C++14)

/**
 * NOI Style Solution for Two Sum II
 * Standard: C++14
 * approach: Two Pointers (双指针)
 */

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 核心逻辑函数
// 输入引用不仅是为了避免拷贝，更是OI中的常见习惯，但在这种小vector上非必须
void solve() {
    int n;
    long long target; // 既然是OI，防一手爆int是好习惯，虽然题目数据范围很小
    
    if (!(cin >> n >> target)) return;

    // 使用 vector 存储，大小预分配
    vector<int> A(n);
    for (int i = 0; i < n; ++i) {
        cin >> A[i];
    }

    // 双指针初始化
    // left 指向数组头部 (下标0)
    // right 指向数组尾部 (下标n-1)
    int left = 0;
    int right = n - 1;

    while (left < right) {
        // 计算当前左右指针所指元素的和
        // 使用 long long 防止极其极端情况下的溢出（虽然本题数据范围不会溢出）
        long long current_sum = (long long)A[left] + A[right];

        if (current_sum == target) {
            // 找到答案，题目要求下标从1开始，所以都要+1
            cout << left + 1 << " " << right + 1 << endl;
            // 题目保证唯一解，找到即可结束
            return;
        } 
        else if (current_sum > target) {
            // 和太大了，需要减小和，只能移动右指针让大数变小
            right--;
        } 
        else {
            // 和太小了，需要增大和，只能移动左指针让小数变大
            left++;
        }
    }
    
    // 理论上题目保证有解，不会走到这里
    // 但在比赛中可以输出一个错误标记方便调试
    // cout << "-1 -1" << endl; 
}

int main() {
    // 优化 C++ I/O 速度，NOI/ACM 必备
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    solve();

    return 0;
}

给学生的最后提示

做完这道题，不要马上关掉。请思考一个变式：

如果数组没有排序，但同样要求 $O(1)$ 空间复杂度，还能做到 $O(n)$ 时间吗？ 答案是：不能。没有排序且限制空间，通常只能 $O(n^2)$ 暴力或 $O(n \log n)$ 先排序。 所以，“有序” 是这道题使用双指针 $O(n)$ 解法的灵魂所在。记住这个感觉！