LeetCode 面试题 16.06. 最小差

约 5 分钟
文章信息 11 个分类 4 个标签
分类
LeetCode CodeTop 中等 未解决 5-10 字节跳动 微软 快手 腾讯 拼多多 程序员面试金典（第 6 版）
标签
数组 排序 双指针 二分查找
目录

题目描述

✅ 面试题 16.06. 最小差

题意分析

给两个整数数组，要从第一个数组里挑一个数、从第二个数组里挑一个数，让这两个数之差的绝对值尽可能小，返回这个最小的绝对差。两个数必须来自不同的数组，同一数组内部的两两之差不算数。

题目对数组本身没有任何有序性假设，元素可以重复、可以为负、顺序任意。数组长度上限到十万，两个数组的组合数就是一百亿，这个规模明确排除了枚举全部配对的做法。

最需要警惕的是取值范围：元素可以取到 32 位有符号整数的最小值和最大值，两者相减的真实差值接近 43 亿，远超 int 能表示的范围。这意味着任何在 int 上直接做减法或取绝对值的写法都不安全。另外还要注意，题目保证答案本身能放进 int（因为最小差不可能超过某一对相邻元素的距离，且判题数据如此设计），所以中间用 64 位、返回时转回 32 位是合适的处理方式。

解法：排序 + 双指针

核心思路

问题关键： 暴力枚举两个数组的所有配对需要 $O(mn)$。排序后，当前两个指针所指的数决定了哪一侧可以被安全丢弃。

为什么移动较小值： 若 a[i] < b[j]，那么 a[i] 与 b[j] 右侧任何数的差只会更大，a[i] 已经不可能参与更优答案，应移动 i；反之移动 j。

不变量： 每轮开始时，所有被指针越过的元素可能形成的最小差都已计入 answer；尚未发现的最优配对只可能位于两个指针及其右侧。每次淘汰较小值后，不变量继续成立。

溢出处理： 32 位整数的极小值与极大值之差超过 int。必须先把两个操作数转成 64 位，再做减法和绝对值；“先用 int 相减、再转 long”已经发生了溢出。

解题步骤

  1. 分别将两个数组升序排序。
  2. 两个指针从头开始，每轮用 64 位整数计算当前绝对差并更新答案。
  3. 差为 0 时立即返回，因为 0 已是理论下界。
  4. 移动当前值较小的一侧；任一指针越界时结束。

口述示例： a = [1,2,3,11,15]、b = [8,19,23,127,235]。指针依次比较 1、2、3 与 8，直到比较 11 与 8 得到 3；随后移动 8，剩余值不可能再与它形成更小差，最终答案为 3。

边界说明： 代码会原地排序。若调用方要求保留输入顺序，应先复制数组，代价是 $O(m+n)$ 额外空间。

代码实现

import java.util.Arrays;

class Solution {
    public int smallestDifference(int[] a, int[] b) {
        Arrays.sort(a);
        Arrays.sort(b);

        int i = 0;
        int j = 0;
        long answer = Long.MAX_VALUE;
        while (i < a.length && j < b.length) {
            long first = a[i];
            long second = b[j];
            answer = Math.min(answer, Math.abs(first - second));
            if (answer == 0) {
                return 0;
            }

            if (first < second) {
                i++;
            } else {
                j++;
            }
        }
        return (int) answer;
    }
}

import "sort"

func smallestDifference(a, b []int) int {
    sort.Ints(a)
    sort.Ints(b)

    i, j := 0, 0
    answer := int64(1 << 62)
    for i < len(a) && j < len(b) {
        first, second := int64(a[i]), int64(b[j])
        diff := first - second
        if diff < 0 {
            diff = -diff
        }
        if diff < answer {
            answer = diff
        }
        if answer == 0 {
            return 0
        }

        if first < second {
            i++
        } else {
            j++
        }
    }
    return int(answer)
}

复杂度分析

  • 时间复杂度：$O(m\log m+n\log n)$，排序是主导项；双指针扫描为 $O(m+n)$。
  • 空间复杂度：取决于语言排序实现，通常为 $O(\log m+\log n)$ 的栈空间；双指针本身为 $O(1)$。

关键点总结

  • 排序把全局配对问题转成“淘汰当前较小值”的单向扫描。
  • 每次移动前都要能证明被丢弃元素不可能再形成更优配对。
  • 绝对差涉及整数边界时，必须在减法之前提升到 64 位。
  • 差为 0 可立即结束；若不能修改输入，要明确复制成本。

易错点总结

  • 在 int 中先相减再转 64 位：溢出已经发生，后续转换无法补救。
  • 使用 Math.abs(Integer.MIN_VALUE)：结果仍是负数。
  • 每轮同时移动两个指针：会跳过 (11,8) 这类可能的最优配对。
  • 移动较大值一侧：当前较小值只会离后续元素更远，无法缩小差距。

相似题目

题目 难度 考察点
16. 最接近的三数之和 中等 同为「求最接近」，但固定一个数后在剩余区间用对撞双指针
167. 两数之和 II - 输入有序数组 中等 单数组内两端向中间收缩，移动方向由和的大小决定
349. 两个数组的交集 简单 排序后同向双指针求交集，相等时需跳过重复元素
350. 两个数组的交集 II 简单 交集要保留重复次数，相等时两指针同时前进
88. 合并两个有序数组 简单 同样是两个有序数组的同向扫描，但要原地从后往前写以免覆盖
611. 有效三角形的个数 中等 排序后靠单调性批量统计合法配对，练的是「一次移动排除一批」