上海计算机学会2021年12月月赛C++丙组T4两数之和

要解决这个问题，请判断是否存在两个不同的整数 ai 和 aj（i ≠ j），使得 ai + aj = t。由于给定的整数序列已经是有序排列的，请参考以下方法：
方法思路
我们可以使用双指针法来高效地解决这个问题：
初始化两个指针：一个指向数组的第一个元素 (left)，另一个指向最后一个元素 (right)。
计算当前两个指针对应元素的和 sum：

• 如果 sum 等于 t，则存在满足条件的两个整数对。
• 如果 sum 大于 t，则将右指针左移以减小 sum 的值。
• 如果 sum 小于 t，则将左指针右移以增大 sum 的值。
  继续上述步骤直到找到满足条件的一对整数或左右指针交叉。
  这种方法的时间复杂度为 O(n)，因为我们只需要遍历数组一次即可解决问题。
  解决代码
  cpp #include <iostream> #include <vector> using namespace std; int main() { int n; cin >> n; vector<int> a(n); for(int i = 0; i < n; ++i) { cin >> a[i]; } int t; cin >> t; int left = 0; int right = n - 1; while(left < right) { int sum = a[left] + a[right]; if(sum == t) { cout << "Yes" << endl; return 0; } else if(sum > t) { --right; } else { ++left; } } cout << "No" << endl; return 0; }
  代码解释
  首先读取输入数据并存储到向量 a 中，并

题目描述

设有n个整数a₁,a₂,…,a_n满足a₁ < a₂ < … < a_n，并设定目标值t为已知数值。请判断是否存在两个不同的元素ai和aj满足ai + aj等于t。

输入格式

第一行：单个整数 n；
第二行：n 个整数 a1​,a2​,⋯,an​；
第三行：单个整数 t。

输出格式

• 如果存在一种组合满足要求，输出 Yes；
• 否则，输出 No。

数据范围

• 对于 30% 的数据，1≤n≤3000；
• 对于 60% 的数据，1≤n≤100,000；
• 对于 100% 的数据，1≤n≤1,000,000；
• −1,000,000,000≤ai​≤1,000,000,000；
• −2,000,000,000≤t≤2,000,000,000。

样例数据

输入:
4
1 3 5 7
8
输出:
Yes
说明:
8=3+5
输入:
4
2 4 6 8
11
输出:
No
输入:
3
1 2 5
2
输出:
No
说明:
1+1不是一个符合条件的解法，因为输入数据里只有一个1；
单个2也不能算一个符合条件的解法，因为不配对

解析：基于所述数组有序排列的特点，在算法设计中采用了双指针法进行处理。具体而言，在实现过程中需要寻找两个元素之和等于目标值t的情况，请参考代码中的相关实现细节。

 #include <iostream>

    
 #include <algorithm>
    
 using namespace std;
    
 int a[1000005];
    
 int main()
    
 {
    
     int n,t;
    
     cin>>n;
    
     int pl=1;//左指针指向开头
    
     int pr=n;//右指针指向结尾
    
     for (int i=1;i<=n;i++){
    
     scanf("%d",&a[i]);
    
  
    
     }
    
     cin>>t;
    
     while(pr>pl&&a[pr]+a[pl]!=t){//没凑上且左右指针没有重合
    
     if (a[pr]+a[pl]>t){//和比t大，右指针左移
    
         pr--;
    
     }else if (a[pr]+a[pl]<t){//和比t小，左指针右移
    
         pl++;
    
     }
    
     }
    
     if (pl<pr){//指针未重合，证明凑上了，输出Yes,否则输出No
    
     cout<<"Yes"<<endl;
    
     }else{
    
     cout<<"No"<<endl;
    
     }
    
     return 0;
    
 }