巧用双指针：高效求解两有序数组的最小绝对差（数组的距离）

数组 f 和 g 的元素已分别按从小到大排列。 要求两个数组之间差的绝对值的最小值，即： $$ \min \{ |f[i] - g[j]| \} \quad \text{其中 } 0 \leq i < m,\ 0 \leq j < n $$ 这就是“数组的距离”。 --- ✅ 样例分析 输入： ``` 3 3 1 4 10 -1 3 7 ``` 枚举部分组合： - |1 - (-1)| = 2 - |1 - 3| = 2 - |1 - 7| = 6 - |4 - (-1)| = 5 - |4 - 3| = 1 ← 最小 - |4 - 7| = 3 - …… 最小值是 1 → 输出 `1` --- ✅ 解法：双指针法（推荐） 由于两个数组有序，可以用双指针技巧在 O(m + n) 内解决。 思路： - 指针 i 指向 f 数组 - 指针 j 指向 g 数组 - 比较 f[i] 和 g[j] - 更新最小绝对差 - 移动较小元素的指针（以尝试更接近的值） --- ✅ Python 代码实现 ```python m, n = map(int, input().split()) f = list(map(int, input().split())) g = list(map(int, input().split())) i = 0 j = 0 min_diff = abs(f[0] - g[0]) while i < m and j < n: diff = abs(f[i] - g[j]) if diff < min_diff: min_diff = diff if f[i] < g[j]: i += 1 else: j += 1 print(min_diff) ``` --- 🔍 为什么移动较小的那个？ 因为数组升序排列： - 若 `f[i] < g[j]`，那么想让差更小，只能让 `f[i]` 变大 → i++ - 若 `g[j] <= f[i]`，则让 `g[j]` 变大 → j++ 这样不会遗漏最小值，利用了有序性。 --- ✅ 测试样例验证 f = [1, 4, 10] g = [-1, 3, 7] 初始：i=0, j=0 → |1 - (-1)| = 2 → min_diff=2 1 > -1 → j++ i=0, j=1 → |1 - 3|=2 → min_diff=2 1 < 3 → i++ i=1, j=1 → |4 - 3|=1 → min_diff=1 4 > 3 → j++ i=1, j=2 → |4 - 7|=3 → 不更新 4 < 7 → i++ i=2, j=2 → |10 - 7|=3 → 不更新 10 > 7 → j++ → j 越界 → 结束 输出：1 → 正确 ✅ --- ✅ 输出结果 对于样例输入，输出为： ``` 1 ``` --- 📌 - 输入：两个有序数组 - 目标：求两数组间最小绝对差 - 方法：双指针遍历，O(m + n) - 无需暴力嵌套循环（O(m×n)也可过，但不是最优） 此代码高效、简洁、正确，适合提交评测系统。 ######[AI问答 | 801点数解答 | 2026-01-08 12:16:22]