解答：

方法一：暴力法

用i、j、k三个指针分别表示当前指向数组集合 S1 、 S2 和 S3 中的位置，枚举所有的三元组，取所有三元组中的最小距离。

C代码如下（含测试用例）：

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

int findMinDist(int s1[], int s2[], int s3[], int n1, int n2, int n3) {
    int min_dist = INT_MAX;
    int dist;
    for (int i = 0; i < n1; i++) {
        for (int j = 0; j < n2; j++) {
            for (int k = 0; k < n3; k++) {
                dist = abs(s1[i] - s2[j]) + abs(s2[j] - s3[k]) + abs(s3[k] - s1[i]);
                if (dist < min_dist) {
                    min_dist = dist;
                }
            }
        }
    }
    return min_dist;
}

int main(int argc, const char * argv[]) {
    int s1[3] = {-1, 0, 9};
    int s2[4] = {-25, -10, 10, 11};
    int s3[5] = {2, 9, 17, 30, 41};
    int ans = findMinDist(s1, s2, s3, 3, 4, 5);
    printf("%d\n", ans);
    return 0;
}

复杂度分析

• 时间复杂度： O(n1n2n3) ，其中 n1、n2 和 n3 分别为S1、S2和S3的长度。
• 空间复杂度： O(1) ，中间过程额外需要常数个变量。

如果用暴力法应该能拿到一半多一点的分，也就是本题13分能拿到7-8分。

方法二：同向多指针（滑动窗口变体）

这道题难度非常大，称为408史上第二难算法题毫不过分，本题需要用到多指针或指针数组。

使用i、j、k三个指针分别指向三个数组的首个元素，每次移动三个指针中指向元素最小的指针（三个指针可能交替移动），移动后检查有没有产生更短的距离。这里为同向三指针，将所有元素放到一个数轴上，求最左和最右指针的最小距离，可以理解为广义的求滑动窗口最小值。

C代码如下（含测试用例）：

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

int findMinDist(int s1[], int s2[], int s3[], int n1, int n2, int n3) {
    int min_dist = INT_MAX;
    int dist;
    int i = 0, j = 0, k = 0;
    while (i < n1 && j < n2 && k < n3) {
        dist = abs(s1[i] - s2[j]) + abs(s2[j] - s3[k]) + abs(s3[k] - s1[i]);
        if (dist < min_dist) {
            min_dist = dist;
        }
        if (s1[i] < s2[j]) {
            if (s1[i] < s3[k]) { // s1[i]
                i++;
            } else { // s3[k]
                k++;
            }
        } else {
            if (s2[j] < s3[k]) { // s2[j]
                j++;
            } else {  // s3[k]
                k++;
            }
        }
    }
    return min_dist;
}

int main(int argc, const char * argv[]) {
    int s1[3] = {-1, 0, 9};
    int s2[4] = {-25, -10, 10, 11};
    int s3[5] = {2, 9, 17, 30, 41};
    int ans = findMinDist(s1, s2, s3, 3, 4, 5);
    printf("%d\n", ans);
    return 0;
}

复杂度分析

• 时间复杂度： O(n1+n2+n3) ，其中 n1、n2 和 n3 分别为S1、S2和S3的长度。
• 空间复杂度： O(1) ，中间过程额外需要常数个变量。