题目

定义三元组 (a, b, c)（a, b, c 均为正数）的距离 D = |a - b| + |b - c| + |c - a|。给定 3 个非空整数集合 S₁, S₂, S₃，按升序分别存储在 3 个数组中。请设计一个尽可能高效的算法，计算并输出所有可能的三元组 (a, b, c)（a ∈ S₁, b ∈ S₂, c ∈ S₃）中的最小距离。

例如，S₁ = {-1, 0, 9}，S₂ = {-25, -10, 10, 11}，S₃ = {2, 9, 17, 30, 41}，则最小距离为 2，相应的三元组为 (9, 10, 9)。

要求：

(1) 给出算法的基本设计思想。

(2) 根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释。

(3) 说明你所设计算法的时间复杂度和空间复杂度。

解析

(1) 设计思想

答案：用三指针 i、j、k 分别扫 S₁、S₂、S₃ 三个有序数组；每轮计算当前三元组距离，更新最优值；然后让指向当前三元组最小元素的那个指针前进一位（其他两个不动）；任一指针越界即停止。

关键化简——把"三个绝对值之和"变成"max − min"。设 a, b, c 中最小为 m，最大为 M（即 mid 是另一个）。不妨设 a ≤ b ≤ c：

也就是说 D 与中间那个数无关，只取决于 max 和 min。所以问题简化为：在三数组各取一个，让 max−min 最小。

为什么移动"最小者"才对？

当前三元组 (a, b, c)，记 m = min。三个数组都升序，所以 m 所在数组的指针只能向后增大或保持。让 m 变大，max−min 才有机会缩小。反过来，移动 max 所在指针只会让 max 更大或不变（不会减小），距离不会变小；移动 mid 不影响 max 和 min，距离不变（只会浪费一步）。所以每轮唯一正确的选择就是动 min 那一个。

任一数组扫完即停止——再也找不到更小的 min 了。

(2) 代码实现

#include <limits.h>

int minDist(int A[], int n1, int B[], int n2, int C[], int n3) {
    int i = 0, j = 0, k = 0;
    long long best = LLONG_MAX;

    while (i < n1 && j < n2 && k < n3) {
        int a = A[i], b = B[j], c = C[k];

        // 当前三元组的 max 和 min
        int mn = a < b ? a : b;  if (c < mn) mn = c;
        int mx = a > b ? a : b;  if (c > mx) mx = c;

        // 距离 = 2*(max - min)；用 long long 防极端值溢出
        long long d = 2LL * (mx - mn);
        if (d < best) best = d;
        if (best == 0) return 0;        // 三数相等时距离 0，已最优可提前返回

        // 移动 min 所在指针；若并列则任意挑一个先动
        if (a == mn) i++;
        else if (b == mn) j++;
        else k++;
    }

    return (int) best;
}

关键点说明：

• 移动 min 而非 max：很多人第一反应是"哪个最大就动哪个让它变小"——但数组升序，指针向后只增不减，max 只会越来越大。只有 min 这一侧动了，max−min 才有机会缩。
• 任一数组扫完即停：循环条件是 i<n1 && j<n2 && k<n3，任何一个指针越界整体停止。原因：那个数组的元素已用完，再换其他两边的元素只会让 min（已固定为越界数组当前指针前的最大元素）的对手变得更大，min−那一边的距离不会变小。
• d = 2 * (mx - mn) 用 long long：max 和 min 都可能接近 INT 边界，相减再 ×2 有溢出风险；考研评分一般不深究但工程上必加。
• 题面"a,b,c 均为正数"与示例矛盾：题干说"正数"，但例子里有 −1、0、−25 等负数。按例子写就对——算法对负数也成立。

(3) 复杂度分析

设三个数组长度分别为 。

• 时间复杂度 ：每轮循环 i、j、k 中有且仅有一个指针前进一位，三个指针总前进次数不会超过 。每轮内部是常数次比较和算术。
• 空间复杂度 ：除入参数组外只用了 i、j、k、a、b、c、mn、mx、best、d 等几个标量，与输入规模无关。