1244：和为给定数——尺取法

【题目描述】
给出若干个整数，询问其中是否有一对数的和等于给定的数。

【输入】
第一行是整数n(0

第二行是n个整数。整数的范围是在0到108之间。

第三行是一个整数m（0≤m≤230)，表示需要得到的和。

【输出】
若存在和为m的数对，输出两个整数，小的在前，大的在后，中间用单个空格隔开。若有多个数对满足条件，选择数对中较小的数更小的。若找不到符合要求的数对，输出一行No。

【输入样例】
4
2 5 1 4
6
【输出样例】
1 5

分析

1. 一看n的数据范围，暴力就不行（一个for从i开始，一个fori从i+1），然后用尺取法，和双指针差不多，一个指向前，一个指向后，两数之和大了，右指针前移，两数之和小了，左指针后移，至到相等为止，输出答案；
2. 也可以一个指针指向前面，然后二分另一个数的指针，进行同样的操作判断；注意想要使用二分或者尺取法，就要先给数组进行排序，可以用stl的函数，也可以手写排序；
3. 此题没有卡爆int的测试点，两数相加，在极端条件下可能会爆int，所以留个心；

#includeusing namespace std;
int n, m;
int a[100005];int main() {std::ios::sync_with_stdio(false);cin.tie(nullptr);cin >> n;for (int i = 0; i < n; ++i) {cin >> a[i];}cin >> m;sort(a, a + n);int l = 0, r = n - 1;while (l < r) {if (a[l] + a[r] == m) {cout << a[l] << " " << a[r];return 0;}if (a[l] + a[r] > m) {//a[r]大了r--;} else {l++;}}cout << "No";return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！