AcWing 800. 数组元素的目标和

AcWing 800. 数组元素的目标和 - 糖豆爸爸 - 博客园
AcWing 800. 数组元素的目标和 - AcWing - 四种做法 *

---

AcWing 800. 数组元素的目标和 [简单]

1 题目描述

给定两个升序排序的有序数组 A 和 B，以及一个目标值 x。

数组下标从 0 开始。

请你求出满足 A[i] + B[j] = x 的数对 (i, j)。

数据保证有唯一解。

输入格式
第一行包含三个整数 n, m, x，分别表示 A 的长度，B 的长度以及目标值 x。

第二行包含 n 个整数，表示数组 A。

第三行包含 m 个整数，表示数组 B。

输出格式
共一行，包含两个整数 i 和 j。

数据范围
数组长度不超过 105。
同一数组内元素各不相同。
1 ≤ 数组元素 ≤ 109

输入样例：

4 5 6
1 2 4 7
3 4 6 8 9

输出样例：

1 1

2 解题思路

2.1 暴力

毫无疑问: TLE.

for (int i = 0; i < n; i ++ ){
        for (int j = 0; j < m; j ++ ){
            if (a[i] + b[j] == x)
                cout << i << " " << j;
        }
    }

2.2 双指针

• 时间复杂度 O(n + m)

让 i 指向 0 , 定义 j 为 a[i] + b[j] >= x 的最左边界, 起初指向 m - 1. 当 i ++ 时, a[i] 增大, 由于总和不变, b[j] 必须减小, 所以 j 只要一直减小, 不用回退

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

const int N = 100010;
int n, m, x;
int a[N], b[N];

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    
    cin >> n >> m >> x;
    // 读入a,b两个数组, 注意它们两个都是升序的
    for (int i = 0; i < n; i ++ ) cin >> a[i];
    for (int j = 0; j < m; j ++ ) cin >> b[j];
    
    // min a, max b, a + b = x, a+ -> b-
    // 从 i = 0 和 j = m - 1 开始枚举
    for (int i = 0, j = m - 1; i < n; i ++ ) {
        while (j > 0 && a[i] + b[j] > x) j -- ;
        if (a[i] + b[j] == x) {
            cout << i << " " << j << endl;
            break;
        }
    }
    
    return 0;
}

• 其实思路就是:

• 初始时 i = 0, j -- 直到找到第一个满足 a[0] + b[j] <= x 的位置;
• 若找不到则 j 保持初值不变,判断此时满不满足条件,
• 若找到了, 则 j 暂时固定不变然后 i ++ 找下一轮;
• 循环中可以向着答案慢慢调整 j 值 (j 如果取大了会触发循环, 把 j 减小);

• 时间复杂度只有 O(n + m);
  这个设计其实可以输出所有可行解, 若没保证唯一解又只要一组解可以 break;
  解不唯一时的测试样例如下

  5 4 7
  1 2 4 5 6
  1 2 3 4

• 错误解法:

for(int i = 0, j = 0; i < n; i ++ ) {
    while (a[i] + b[j] < x && j < m)    j ++ ;                 
    if (a[i] + b[j] == x && j < m)
        cout << i << ' ' << j << endl;
}

• j 从 0 开始增大, 找到第一个 >=x 的位置;
• 若找不到, 则 i++ 找下一轮;
• 找到 j 后再增大 i , 那么之后的结果一定大于 x ;
• 即 j 不能再通过循环向着正确答案调整 ( j 锁定了);
• 若锁定的 j 不是正确值则将永远得不出正解;

2.3 二分 *

大佬的做法: AcWing 800. 数组元素的目标和 - AcWing

时间复杂度 O(nlogm)

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

const int N = 100010;
int n, m, x;
int a[N], b[N];

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    cin >> n >> m >> x;

    for (int i = 0; i < n; i ++) cin >> a[i];
    for (int i = 0; i < m; i ++) cin >> b[i];

    for (int i = 0; i < n; i ++) {
        int l = 0, r = m - 1;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (a[i] + b[mid] <= x) l = mid;
            else r = mid - 1;
        }
        if (a[i] + b[l] == x) {
            cout << i << ' ' << l << '\n';
            break;
        }
    }

    return 0;
}

2.4 利用单调性的二分 *

大佬的做法: AcWing 800. 数组元素的目标和 - AcWing

时间复杂度 O(n + logm)

找 j 花费的总时间为 logm + log(m/2) + log(m/4) + ... + log2 ~ logm. 加上 i ++ 次数, 得 O(n + logm)

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

const int N = 1e5 + 5;
int n, m, x;
int a[N], b[N];

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    cin >> n >> m >> x;

    for (int i = 0; i < n; i ++ ) cin >> a[i];
    for (int i = 0; i < m; i ++ ) cin >> b[i];

    // min a, max b, a + b = x, a+ -> b-
    for (int i = 0, j = m - 1; i < n; i ++ ) {
        int l = 0, r = j;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (a[i] + b[mid] <= x) l = mid;
            else r = mid - 1;
        }
        j = l;
        if (a[i] + b[j] == x) {
            cout << i << ' ' << j << '\n';
            break;
        }
    }

    return 0;
}

2.5 双向二分 *

大佬的做法: AcWing 800. 数组元素的目标和 - AcWing

时间复杂度 O(logn + logm)

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

const int N = 1e5 + 5;
int n, m, x;
int a[N], b[N];

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    cin >> n >> m >> x;

    for (int i = 0; i < n; i ++ ) cin >> a[i];
    for (int i = 0; i < m; i ++ ) cin >> b[i];

    // min a, max b, a + b = x, a+ -> b-
    for (int i = 0, j = m - 1; i < n;) {
        int l = 0, r = j;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (a[i] + b[mid] <= x) l = mid;
            else r = mid - 1;
        }
        j = l;
        if (a[i] + b[j] == x) {
            cout << i << ' ' << j << '\n';
            break;
        }

        l = i, r = n - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (a[mid] + b[j] >= x) r = mid;
            else l = mid + 1;
        }
        i = l;
        if (a[i] + b[j] == x) {
            cout << i << ' ' << j << '\n';
            break;
        }
    }

    return 0;
}