两数之和

课程自编 · 相向双指针

题目描述

给出一个长度为 $n$ 的非递减整数序列 $a_1,a_2,\dots,a_n$ 和目标整数 $T$。判断是否存在两个下标 $i<j$，使得 $a_i+a_j=T$。

输入格式

第一行两个整数 $n,T$。第二行 $n$ 个整数，保证非递减。

输出格式

如果存在，输出一行 Yes；否则输出一行 No。

数据范围与约定

$1 \le n \le 2\times 10^5$，$|a_i| \le 10^9$，$|T| \le 2\times 10^9$，且 $a_1 \le a_2 \le \cdots \le a_n$。

样例输入

6 9
1 2 4 5 6 8

样例输出

Yes

样例说明

$4+5=9$，存在合法的一对，因此输出 Yes。相向双指针从两端开始，根据当前和与 $T$ 的大小关系移动左端或右端。

说明

课程自编题，数据由 src/gen.py 生成。