题目描述

有两个严格升序数组，要求这两数组中各取一数，唯一满足a[i] + b[j] = x；输出这两个数的下标；

样例

10 10 30
9 13 15 19 20 26 40 43 44 49
1 5 6 21 22 28 31 32 46 49

算法1

双指针法(一头一尾指针) $O(n)$

使用双指针，一只指针i从一个数组a[]的头部开始遍历，另一只j从另一个数组b[]的尾部开始遍历，如果两指针指向的数相加小于x，则指针i右移；若大于x，则指针j左移；

时间复杂度 $O(n)$

C++ 代码

#include<iostream>
using namespace std;

const int N = 100010;
int a[N], b[N];

int main()
{
    int n, m, x;
    cin>>n>>m>>x;
    for(int i = 0; i < n; ++i)
        scanf("%d", &a[i]);
    for(int i = 0; i < m; ++i)
        scanf("%d", &b[i]);
    int i = 0, j = m-1;
    while(a[i]+b[j] != x)
    {
        if(a[i] + b[j] < x)
            ++i;
        else
            --j;
    }
    cout<<i<<' '<<j;
    return 0;
}

算法2

双指针法(两个指针同向) $O(n)$

实际还是一头一尾指针，只不过尾指针是从数组头部开始遍历，直到寻找到使a[i] + b[j] > x时停止，再往回退；

时间复杂度 $O(n)$

C++ 代码

#include<iostream>
using namespace std;

const int N = 100010;
int a[N], b[N];

int main()
{
    int n, m, x;
    cin>>n>>m>>x;
    for(int i = 0; i < n; ++i)
        scanf("%d", &a[i]);
    for(int i = 0; i < m; ++i)
        scanf("%d", &b[i]);
    int i = 0, j = 0;     //这里是两个头部指针
    while(i < n-1 && a[i]+b[j] < x)
        ++i;              //将i递增，达到使两数相加大于x时停止，并向回走；
    while(a[i]+b[j] != x)
    {
        if(a[i] + b[j] < x)
            ++j;          //j作为递增指针
        else
            --i;          //i向回走
    }
    cout<<i<<' '<<j;
    return 0;
}