A18812. 对撞双指针
填空题
较难
知识点
题目描述
对撞双指针
题目描述
给定严格升序数组，找出两个不同下标数字相加等于target，输出两个下标，保证唯一解。
输入
第一行 n target
第二行 n 个升序整数
输出：两个从小到大的下标
数据范围：2 le n le 1000
样例输入
5 12
2 4 5 7 9样例输出
1 4要求
必须使用对撞双指针，禁止二重循环暴力。
参考答案
#include <iostream>
using namespace std;
int a[1005];
int main()
{
int n, tar;
cin >> n >> tar;
for(int i = 0; i < n; i++)
cin >> a[i];
int l = 0, r = n - 1;
while(l < r)
{
int sum = a[l] + a[r];
if(sum == tar)
{
cout << l << " " << r;
break;
}
else if(sum < tar)
l++;
else
r--;
}
return 0;
}
上一题
下一题