一、题目来源
AcWing算法基础课-800.数组元素的目标和
二、题目描述
给定两个升序排序的有序数组 (A) 和 (B),以及一个目标值 (x)。
数组下标从 (0) 开始。
请你求出满足 (A[i] + B[j] = x) 的数对 ((i,j))。
数据保证有唯一解。
输入格式
第一行包含三个整数 (n,m,x) 分别表示 (A) 的长度,(B) 的长度以及目标值 (x)。
第二行包含 (n) 个整数,表示数组 (A)。
第三行包含 (m) 个整数,表示数组 (B)。
输出格式
共一行,包含两个整数 (i) 和 (j)。
数据范围
数组长度不超过 (10^5)。
同一数组内元素各不相同。
(1≤数组元素≤10^9)
输入样例:
4 5 6
1 2 4 7
3 4 6 8 9
输出样例:
1 1
三、算法思路
本题使用双指针来解决问题。
思路如下:
-
(i) 指针从 (a) 数组的左边开始枚举, (j) 指针从 (b) 数组的右边开始枚举。
-
由于两个数组都是有序的,且答案唯一,所以如果此时 (a[i] + b[j] > x)的话,则减小 (b[j]),直到不满足(a[i] + b[j] > x)。
1)如果当前(a[i] + b[j] = x) 则直接输出即可。
2)如果当前(a[i] + b[j] 则增大 (a[i]) 即可,并重复2.。
-
如此遍历一遍,(i) 不会往左走, (j) 不会往右走,两个数组都只会遍历一遍即可找出答案,即时间复杂度为 (O(m + n))。
- 如果用暴力解题的话,两层 (for) 循环,时间复杂度 (O(n ^ 2))。
- 其次,此题两个数组都是有序的,而且答案唯一,这样才能用双指针来优化。
四、源代码
#include
using namespace std;
const int N = 100010;
int n, m, x;
int a[N], b[N];
int main()
{
cin >> n >> m >> x;
for (int i = 0; i > a[i];
for (int i = 0; i > b[i];
for (int i = 0, j = m - 1; i x) -- j;
if (a[i] + b[j] == x)
{
cout
机房租用,北京机房托管,大带宽租用,IDC机房服务器主机租用托管-价格及服务咨询 www.e1idc.net