LeetCode 面试题 16.06. 最小差

Categories:

题目描述
思路分析
1. 解法一：排序 + 双指针（推荐）
相似题目

题目描述

✅ 面试题 16.06. 最小差

思路分析

解法一：排序 + 双指针（推荐）

核心思路：

将两个数组分别排序。

使用双指针同时向右移动，更新最小差值。

每次移动较小值所在的指针以缩小差距。

复杂度分析：

时间复杂度：O(m log m + n log n)，其中 m、n 为数组长度。

空间复杂度：O(1) 或 O(log n)，排序带来的额外空间。

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

        int i = 0;
        int j = 0;
        long ans = Long.MAX_VALUE;

        // 双指针缩小差距
        while (i < a.length && j < b.length) {
            long diff = (long) a[i] - b[j];
            ans = Math.min(ans, Math.abs(diff));

            if (diff < 0) {
                i++;
            } else {
                j++;
            }
        }

        return (int) ans;
    }
}

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

	i, j := 0, 0
	ans := int64(^uint64(0) >> 1)

	// 双指针缩小差距
	for i < len(a) && j < len(b) {
		diff := int64(a[i]) - int64(b[j])
		if diff < 0 {
			diff = -diff
		}
		if diff < ans {
			ans = diff
		}

		if a[i] < b[j] {
			i++
		} else {
			j++
		}
	}

	return int(ans)
}

相似题目

题目	难度	考察点
16. 最接近的三数之和	中等	排序 + 双指针
532. 数组中的 k-diff 数对	中等	排序
633. 平方数之和	中等	双指针
977. 有序数组的平方	简单	双指针
面试题 16.06. 最小差	中等	排序

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/78509246