2020·41 三元组最小距离：从三重循环到三指针

本文属于「从暴力解到最优解」专题。套路照旧：先把暴力解写对 → 按判分口径估分 → 找浪费 → 升级成最优解。

题目

定义三元组 (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) 说明你所设计算法的时间复杂度和空间复杂度。

题面写了「尽可能高效」，暴力解和最优解之间存在真实分差。总分 8 分。另外注意一个题面小瑕疵：题干说 a, b, c 均为正数，示例里却有 −1、−25 这样的负数——按示例写就对，算法对负数照样成立。

第一步：把暴力解写对

「所有可能的三元组中的最小距离」——考场上最自然的第一反应就是把「所有可能」四个字直译成代码：三层循环，把每个 (a, b, c) 组合都拼出来，按定义算距离，一路打擂台取最小：

#include <limits.h>

int absDiff(int x, int y) { return x > y ? x - y : y - x; }

int minDist(int A[], int n1, int B[], int n2, int C[], int n3) {
    long long best = LLONG_MAX;                 // 初值必须比任何真实距离都大
    for (int i = 0; i < n1; i++)
        for (int j = 0; j < n2; j++)
            for (int k = 0; k < n3; k++) {      // 枚举全部 n1*n2*n3 个三元组
                long long d = (long long)absDiff(A[i], B[j])
                            + absDiff(B[j], C[k])
                            + absDiff(C[k], A[i]);
                if (d < best) best = d;
            }
    return (int)best;
}

拿题面的例子验证：3 × 4 × 5 = 60 个组合全部试过，最小值出现在 (9, 10, 9)，D = 1 + 1 + 2 = 2 ✓。这份代码几乎没有可错的地方——不依赖升序、不需要任何洞察，唯一要留神的是 best 初值要用足够大的值（LLONG_MAX），否则第一轮更新之前就可能出错。

复杂度：设三个数组长度为 p、q、r，三层循环 $O(pqr)$；只有几个标量，空间 $O(1)$。

它值多少分

按正确性/最优性两个维度（详见总纲）：

• 正确性：全枚举不漏任何组合，结果必然正确；思路直白说得清，复杂度照实写 $O(pqr)$，分析与实现一致。正确性维度的分拿得到。
• 最优性：题面要求「尽可能高效」，这道题的期望是线性 $O(p+q+r)$。三个长度相乘与三个长度相加，差距是量级级别的，最优性那档拿不到。

暴力解拿正确性分、丢最优性分。这道题总分 8 分，暴力解保底之后，剩下的分差就看能不能完成下面两个观察。

暴力解的浪费在哪

用总纲的三个问题审一遍，这道题在两处中招：

有没有放着性质不用？——最大的浪费。题面白纸黑字写着三个数组按升序存储，暴力解却把它们当无序集合全枚举。有序意味着「从小到大」这条信息免费送到手上，一次没用。

**有没有重算已知的东西？——定义层面也有一处。**把距离公式拆开看：设当前三元组从小到大是 m ≤ mid ≤ M，则

$$D=(mid-m)+(M-mid)+(M-m)=2(M-m)$$

**距离与中间那个数完全无关，只由 max 和 min 决定。**暴力解每轮老老实实算三个绝对值，其中一份信息纯属多余。化简之后问题瘦身成：三个数组各取一个数，让 max − min 最小。

两个观察拼在一起就是升级路线：只需要盯住当前三元组的 min 和 max，而升序保证每个数组的指针只会向大的方向走——于是每一步该动谁，答案是唯一的。

智慧化改造：每轮只推进最小者

三个指针 i、j、k 各指向一个数组的开头，每轮做两件事：算当前三元组的距离更新最优值；然后让指向当前最小元素的那个指针前进一位，其余两个不动。任何一个指针越界就停。

为什么动 min 是唯一正确的选择？当前三元组 (a, b, c)，数组升序，指针向后只增不减：

• 动 max 所在指针：max 只会更大或不变，max − min 不可能缩小，纯亏；
• 动 mid 所在指针：min 和 max 都没变，距离不变，浪费一步；
• 动 min 所在指针：min 有机会抬高，max − min 才可能缩小——这是唯一有希望改善答案的动作。

任一数组扫完即停：更小的 min 候选已经不存在了。

#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 动了只会更大。方向搞反，整个算法就错了。
• 退出条件是 && 串联：i < n1 && j < n2 && k < n3，任何一个指针越界整体停止。手一滑写成 || 会带着越界下标继续读数组。
• min 并列不用纠结：三数相等或两数并列最小时，if-else 链自然挑一个先动，下一轮再动另一个，不影响正确性。
• 2 * (mx - mn) 用 long long：max 和 min 都可能接近 int 边界，相减再乘 2 有溢出风险；考研评分一般不深究，工程上必加。
• best == 0 提前返回是可选优化，不写也不影响。

复杂度：每轮循环有且仅有一个指针前进一位，三个指针总前进次数不超过 $p+q+r$，时间 $O(p+q+r)$——这个「每轮恰好推进一格」的摊还依据要在第 (3) 问里写出来。空间 $O(1)$，只有几个标量。

两版对照跑一遍

用题面的例子（答案 2），先看三重循环——60 个组合一个不落地全试：

加载可视化中...

再看三指针版——每轮推进当前最小者，十来步就收敛到 (9, 10, 9)：

加载可视化中...

演示为 JavaScript 版本，逻辑与上文 C 代码一一对应。

等价方法与升级空间

• 两层枚举 + 二分：固定 a、b，在第三个数组里二分找最接近的 c，$O(pq\log r)$。比全枚举好一档，用上了有序但只用了一半（二分查找），没用到「三个指针可以同步单调推进」这层。正确性有，最优性仍然够不到线性。
• 不化简 D 直接算三个绝对值：三指针框架下每轮算 |a−b|+|b−c|+|c−a| 结果一样对，但「距离只由 max/min 决定」这个化简是设计思想的核心表述之一——想不到它，「为什么动 min」的论证也会跟着说不透。
• 移动 min 的完整论证要在第 (1) 问写全四件事：数组升序、指针只能向后；动 min 才可能缩小距离；动 max 让 max 更大无益；动 mid 距离不变。这段话就是这道题设计思想的主体。

下一步

• 在 OJ 上把两版代码都提交跑一遍：ds-2020-41 三元组最小距离
• 回到题库看这道题的完整解析与错因：真题库 · 数据结构