华为OD机试 - 两个集合输出距离最近的数字 - 双指针（Python/JS/C/C++ 2025 B卷 100分）

2025B卷华为OD机试统一考试题库清单（持续收录中）以及考点说明（Python/JS/C/C++）。

专栏导读

本专栏收录于《华为OD机试真题（Python/JS/C/C++）》。

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新。

一、题目描述

同一个数轴x有两个点的集合A={A1,A2,…,Am}和B={B1,B2,…,Bm}，A(i)和B(i)均为正整数，A、B已经按照从小到大排序，AB均不为空，给定一个距离R，R是正整数。

列出同时满足以下条件的(A(i),B(j))数对：

1、A(i) < B(j)
2、A(i),B(i)之间距离小于等于R

在情况1、2的情况下每个A(i)只能输出距离最近的B(j)

输出结果按A(i)从小到大排序

二、输入描述

第一行输入三个正整数m n R
第二行m个正整数，表示集合A
第三行n个正整数，表示集合B

以空格隔开。

输入限制 1<=R<=100000, 1<=n,m<=100000, 1<= A(i),B(j) <= 1000000000

三、输出描述

每组数对输出一行 A(i)和B(j)

以空格隔开

四、测试用例

测试用例1

1、输入

3 4 5
1 6 10
2 7 11 15

2、输出

1 2
6 7
10 11

3、说明

A[0]=1: B[0]=2。2-1=1 <= 5。输出 (1,2)。

A[1]=6: B[1]=7。7-6=1 <= 5。输出 (6,7)。

A[2]=10: B[2]=11。11-10=1 <= 5。输出 (10,11)。

测试用例2

1、输入

3 3 10
10 20 30
1 2 3

2、输出

3、说明

A[0]=10: ptrB会遍历完B，但B中所有元素都小于10。ptrB到达B的末尾，主循环终止。没有输出。

五、解题思路

1、解题思路

问题要求从两个已排序的整数集合 A 和 B 中找出满足特定条件的数对 (A(i), B(j))。根据示例输出推断，条件是：1) 我们寻找的 B(j) 应该大于等于 A(i) (即 B(j) >= A(i)), 2) 它们之间的差 B(j) - A(i) 小于等于 R, 3) 对于每个 A(i)，应选择那个使得差 B(j) - A(i) 最小的 B(j)。

由于集合 A 和 B 都已按从小到大排序，我们可以有效地使用双指针技术来寻找这些数对。一个指针 (ptrA) 遍历集合 A，另一个指针 (ptrB) 遍历集合 B。

2、具体步骤

初始化两个指针：ptrA = 0 (指向集合 A 的第一个元素) 和 ptrB = 0 (指向集合 B 的第一个元素)。
当 ptrA 没有遍历完集合 A 并且 ptrB 没有遍历完集合 B 时，执行以下循环：

获取集合 A 的当前元素 currentA = A[ptrA]。

调整 ptrB：向前移动 ptrB，直到 B[ptrB] 大于或等于 currentA (B[ptrB] >= currentA)，或者 ptrB 到达了集合 B 的末尾。
这一步的目的是为 currentA 在 B 中找到第一个可能的候选配对元素。

检查 ptrB 是否越界：如果在上一步中 ptrB 到达了集合 B 的末尾，这意味着对于当前 currentA 以及 A 中所有后续的元素，在 B 中都不可能再找到大于或等于它们的元素了。因此，可以终止主循环。

检查距离条件：获取集合 B 的当前元素 currentB = B[ptrB]。计算它们之间的差值 diff = currentB - currentA。
如果 diff <= R：这表示找到了一个有效的数对 (currentA, currentB)。

因为 B 是排序的，并且 ptrB 指向的是第一个满足 B[j] >= currentA 的元素，所以这个 currentB 必然是使得差值 currentB - currentA 最小的那个。输出这个数对。

然后，将 ptrA 向后移动一位，去处理集合 A 中的下一个元素。 ii. 如果 diff > R：这表示 currentB 对于 currentA 来说太远了。由于集合 B 是排序的，ptrB 之后的所有 B 元素与 currentA 的差值将会更大或相等。

因此，当前的 currentA 不可能在 B 中找到符合条件的配对。将 ptrA 向后移动一位，去处理集合 A 中的下一个元素。ptrB 指针在此情况下不回溯，因为它所指向的 B[ptrB] 或其后的元素可能适用于 A 中下一个（更大的）元素。

当循环结束时，所有满足条件的数对都已经被输出。

六、Python算法源码

# coding=utf-8

def solve():
    # 读取第一行的三个正整数 m, n, R
    m, n, R = map(int, input().split()) # 使用map(int, ...)将输入字符串分割并转换为整数

    # 读取第二行的m个正整数，表示集合A
    A = list(map(int, input().split())) # 将输入转换为整数列表

    # 读取第三行的n个正整数，表示集合B
    B = list(map(int, input().split())) # 将输入转换为整数列表

    # 双指针算法
    ptrA = 0 # 指向集合A当前元素的指针
    ptrB = 0 # 指向集合B当前元素的指针

    # 当两个指针都没有超出各自列表的边界时循环
    while ptrA < m and ptrB < n:
        # 移动ptrB，直到找到第一个 B[ptrB] >= A[ptrA] 的元素，
        # 或者ptrB到达列表B的末尾
        while ptrB < n and B[ptrB] < A[ptrA]:
            ptrB += 1 # ptrB向后移动

        # 如果ptrB到达列表B的末尾，说明对于当前的A[ptrA]以及A中后续所有元素，
        # 在B中都找不到合适的（即大于或等于A[ptrA]的）元素了，因此跳出主循环
        if ptrB == n:
            break

        # 此时，我们有 B[ptrB] >= A[ptrA]
        # 检查它们之间的距离是否小于等于R
        if B[ptrB] - A[ptrA] <= R:
            # 条件满足：B[ptrB] >= A[ptrA] 且 B[ptrB] - A[ptrA] <= R
            # 输出数对
            print(str(A[ptrA]) + " " + str(B[ptrB]))
            ptrA += 1 # 处理集合A中的下一个元素
        else:
            # 条件不满足：B[ptrB] - A[ptrA] > R
            # 这意味着对于当前的A[ptrA]，B[ptrB]以及B中后续的元素都太远了。
            ptrA += 1 # 处理集合A中的下一个元素

# 调用解决函数
solve()

七、JavaScript算法源码

// JavaScript通常在浏览器中运行，或者使用Node.js在服务器端运行。
// 以下代码适用于Node.js环境，使用readline模块处理控制台输入。
// 如果在其他环境（如在线判题系统），输入方式可能不同。

const readline = require('readline'); // 引入readline模块用于读取行

const rl = readline.createInterface({ // 创建readline接口实例
    input: process.stdin,       // 设置输入流为标准输入
    output: process.stdout,     // 设置输出流为标准输出 (虽然这里我们主要用console.log)
    terminal: false             // 表明不是一个TTY终端，适用于管道输入
});

let inputLines = []; // 用于存储所有输入行

rl.on('line', (line) => { // 监听'line'事件，每当读取到一行时触发
    inputLines.push(line); // 将读取到的行添加到数组
});

rl.on('close', () => { // 监听'close'事件，当输入流结束时触发
    // 解析第一行的三个正整数 m, n, R
    const [m, n, R] = inputLines[0].split(' ').map(Number); // 分割字符串并转换为数字

    // 解析第二行的m个正整数，表示集合A
    const A = inputLines[1].split(' ').map(Number); // 分割字符串并转换为数字数组

    // 解析第三行的n个正整数，表示集合B
    const B = inputLines[2].split(' ').map(Number); // 分割字符串并转换为数字数组

    // 双指针算法
    let ptrA = 0; // 指向集合A当前元素的指针
    let ptrB = 0; // 指向集合B当前元素的指针

    // 当两个指针都没有超出各自数组的边界时循环
    while (ptrA < m && ptrB < n) {
        // 移动ptrB，直到找到第一个 B[ptrB] >= A[ptrA] 的元素，
        // 或者ptrB到达数组B的末尾
        while (ptrB < n && B[ptrB] < A[ptrA]) {
            ptrB++; // ptrB向后移动
        }

        // 如果ptrB到达数组B的末尾，说明对于当前的A[ptrA]以及A中后续所有元素，
        // 在B中都找不到合适的（即大于或等于A[ptrA]的）元素了，因此跳出主循环
        if (ptrB === n) {
            break;
        }

        // 此时，我们有 B[ptrB] >= A[ptrA]
        // 检查它们之间的距离是否小于等于R
        if (B[ptrB] - A[ptrA] <= R) {
            // 条件满足：B[ptrB] >= A[ptrA] 且 B[ptrB] - A[ptrA] <= R
            // 输出数对
            console.log(`${A[ptrA]} ${B[ptrB]}`);
            ptrA++; // 处理集合A中的下一个元素
        } else {
            // 条件不满足：B[ptrB] - A[ptrA] > R
            // 这意味着对于当前的A[ptrA]，B[ptrB]以及B中后续的元素都太远了。
            ptrA++; // 处理集合A中的下一个元素
        }
    }
});

八、C算法源码

#include <stdio.h> // 引入标准输入输出头文件
#include <stdlib.h> // 为了 malloc 和 free (如果需要动态分配，但这里用固定大小或VLA)

int main() {
    int m, n, R; // 定义变量存储m, n, R
    // 读取第一行的三个正整数 m, n, R
    scanf("%d %d %d", &m, &n, &R); // 从控制台读取整数

    int A[m]; // 定义数组A (使用变长数组VLA，C99及以上标准支持)
              // 如果编译器不支持VLA或有严格限制，应使用动态内存分配 (malloc)
    // 读取第二行的m个正整数，表示集合A
    for (int i = 0; i < m; i++) {
        scanf("%d", &A[i]); // 读取A的每个元素
    }

    int B[n]; // 定义数组B (使用变长数组VLA)
    // 读取第三行的n个正整数，表示集合B
    for (int i = 0; i < n; i++) {
        scanf("%d", &B[i]); // 读取B的每个元素
    }

    // 双指针算法
    int ptrA = 0; // 指向集合A当前元素的指针
    int ptrB = 0; // 指向集合B当前元素的指针

    // 当两个指针都没有超出各自数组的边界时循环
    while (ptrA < m && ptrB < n) {
        // 移动ptrB，直到找到第一个 B[ptrB] >= A[ptrA] 的元素，
        // 或者ptrB到达数组B的末尾
        while (ptrB < n && B[ptrB] < A[ptrA]) {
            ptrB++; // ptrB向后移动
        }

        // 如果ptrB到达数组B的末尾，说明对于当前的A[ptrA]以及A中后续所有元素，
        // 在B中都找不到合适的（即大于或等于A[ptrA]的）元素了，因此跳出主循环
        if (ptrB == n) {
            break;
        }

        // 此时，我们有 B[ptrB] >= A[ptrA]
        // 检查它们之间的距离是否小于等于R
        if (B[ptrB] - A[ptrA] <= R) {
            // 条件满足：B[ptrB] >= A[ptrA] 且 B[ptrB] - A[ptrA] <= R
            // 输出数对
            printf("%d %d\n", A[ptrA], B[ptrB]);
            ptrA++; // 处理集合A中的下一个元素
        } else {
            // 条件不满足：B[ptrB] - A[ptrA] > R
            // 这意味着对于当前的A[ptrA]，B[ptrB]以及B中后续的元素都太远了。
            ptrA++; // 处理集合A中的下一个元素
        }
    }

    return 0; // 程序正常结束
}

九、C++算法源码

#include <iostream> // 引入输入输出流头文件
#include <vector>   // 引入向量（动态数组）头文件
#include <string>   // 引入字符串处理（如果需要，但这里直接用cin）
#include <sstream>  // 引入字符串流（如果需要复杂行解析，但这里直接用cin）

int main() {
    // 为了提高cin/cout的效率，可以解除与stdio的同步（在竞赛中常用）
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int m, n, R; // 定义变量存储m, n, R
    // 读取第一行的三个正整数 m, n, R
    std::cin >> m >> n >> R; // 从控制台读取整数

    std::vector<int> A(m); // 使用vector定义动态数组A，大小为m
    // 读取第二行的m个正整数，表示集合A
    for (int i = 0; i < m; ++i) {
        std::cin >> A[i]; // 读取A的每个元素
    }

    std::vector<int> B(n); // 使用vector定义动态数组B，大小为n
    // 读取第三行的n个正整数，表示集合B
    for (int i = 0; i < n; ++i) {
        std::cin >> B[i]; // 读取B的每个元素
    }

    // 双指针算法
    int ptrA = 0; // 指向集合A当前元素的指针
    int ptrB = 0; // 指向集合B当前元素的指针

    // 当两个指针都没有超出各自向量的边界时循环
    while (ptrA < m && ptrB < n) {
        // 移动ptrB，直到找到第一个 B[ptrB] >= A[ptrA] 的元素，
        // 或者ptrB到达向量B的末尾
        while (ptrB < n && B[ptrB] < A[ptrA]) {
            ptrB++; // ptrB向后移动
        }

        // 如果ptrB到达向量B的末尾，说明对于当前的A[ptrA]以及A中后续所有元素，
        // 在B中都找不到合适的（即大于或等于A[ptrA]的）元素了，因此跳出主循环
        if (ptrB == n) {
            break;
        }

        // 此时，我们有 B[ptrB] >= A[ptrA]
        // 检查它们之间的距离是否小于等于R
        if (B[ptrB] - A[ptrA] <= R) {
            // 条件满足：B[ptrB] >= A[ptrA] 且 B[ptrB] - A[ptrA] <= R
            // 输出数对
            std::cout << A[ptrA] << " " << B[ptrB] << "\n"; // 使用 "\n" 效率通常比 std::endl 高
            ptrA++; // 处理集合A中的下一个元素
        } else {
            // 条件不满足：B[ptrB] - A[ptrA] > R
            // 这意味着对于当前的A[ptrA]，B[ptrB]以及B中后续的元素都太远了。
            ptrA++; // 处理集合A中的下一个元素
        }
    }

    return 0; // 程序正常结束
}

🏆下一篇：华为OD机试真题 - 简易内存池（Python/JS/C/C++ 2025 B卷 200分）

🏆本文收录于，华为OD机试真题（Python/JS/C/C++）

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新。