题目描述
思路解析
一句话答案：LeetCode 1385 两个数组间的距离值：把 arr2 排序后，arr1 里每个数只需一次二分定位就能判断 [x−d, x+d] 里有没有近邻，省去两两比对。时间 O((m+n)·log n)、空间 O(1)。
两个数组和一个 d，距离值数的是哪种数
给两个整数数组 arr1、arr2 和整数 d。对 arr1 里的数 a，只要 arr2 存在 b 满足 |a − b| ≤ d 就算挨得太近，a 不计；只有 arr2 所有数跟 a 距离都严格大于 d，a 才计入。卡的是 ≤ d，等于 d 也算「近」。距离值就是 arr1 里「找不到近邻」的数的个数。题面 arr1=[4,5,8]、arr2=[10,9,1,8]、d=2 答案是 2。
两两都比一遍，数组一大就比不动了
双层循环最直接：arr1 每个数把 arr2 整排扫一遍逐个算距离，撞到 ≤ d 的就出局，整排没撞到才达标。设 arr1 有 m 个数、arr2 有 n 个数，最坏每个 a 都扫满 arr2，共 m 乘 n 次比对，时间 O(m·n)。两数组都上千时就扫不动了。
把 arr2 排好序，为什么每个数只查一次就够
对某个 x，只关心 [x−d, x+d] 里 arr2 有没有落进来的数。乱放时只能一个个比。排好序后，落进区间的数必然连成一段，只要盯住最靠左的候选——第一个不小于 x−d 的数。它若越过右界 x+d，更大的更够不着；它若不存在，说明 arr2 全比 x−d 还小。这份单调让每个 x 一次二分跳到候选就能下结论。
二分跳到哪个位置，又凭什么一眼定生死
用 bisect_left(arr2, x−d) 拿到下标 i，即第一个不小于 x−d 的位置（lower_bound：排好序后第一个 ≥ 目标）。两种达标：i 等于 len(arr2)，arr2 全小于 x−d，左边空着没近邻；或 arr2[i] 严格大于 x+d，最靠左候选都超右界，也没有。任一成立 x 计入答案；若 arr2[i] 落在 [x−d, x+d] 内，它就是近邻，x 出局。
题面 arr1、arr2、d=2，逐个数查落点
先把 arr2 排序成 [1,8,9,10]，计数从 0 起。x=4：x−d=2，落点为 1，arr2[1]=8 比 x+d=6 大，区间没数，达标，计数到 1。x=5：x−d=3，落点仍 1，arr2[1]=8 大于 x+d=7，达标，计数到 2。x=8：x−d=6，落点仍 1，arr2[1]=8 不大于 x+d=10、也不越界，正落在区间里，是近邻，8 出局。达标的是 4 和 5，距离值 2，与题面对得上。
把「存在近邻」当成计数条件，答案就数成了补集
最易记反：数的是 arr2 里「找不到」近邻的 a，搞混答案就成补集。第二坑：判近邻是 ≤ d 不是 < d，等于 d 也算近要出局，写严格小于会漏掉卡在 d 上的近邻、误判达标。第三处只在 Java：Arrays.binarySearch 未命中返回「负的插入点减一」，得先 i = i < 0 ? -i - 1 : i 还原成插入位置，否则负数当下标越界；Python bisect_left、C++ lower_bound 则直接给插入位置。复杂度：排序 O(n log n)，再对 m 个数各做 O(log n) 二分，合起来 O((m+n)·log n)；空间 O(1)。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢一句:arr1 的每个数,去 arr2 找有没有距离 ≤ 2 的近邻;找不到才达标。下面每帧都在套这句。
总览 · arr1 在上排,arr2 在侧栏：arr1 是上面这排 [3,4,10,7],arr2 放在右边侧栏 [9,8,0,7]。要做的事:把 arr1 的每个数轮流拿出来,到 arr2 里查有没有距离不超过 2 的邻居。一个邻居都没有的才算达标,最后数出有几个。先从第一个数 3 开始。
检查 arr1[0] = 3：现在轮到 arr1 的第 0 个数,值是 3。去 arr2 这排里挨个看,有没有哪个数跟它的距离不超过 2。只要找到一个,3 就出局;一个都没有,它才达标。
比 arr2[0] = 9 · 距离 6：arr2 的第 0 个数是 9,算一下距离 |3 减 9| = 6。6 比 2 大,这个数离得够远,接着看下一个。
比 arr2[1] = 8 · 距离 5：arr2 的第 1 个数是 8,算一下距离 |3 减 8| = 5。5 比 2 大,这个数离得够远,接着看下一个。
比 arr2[2] = 0 · 距离 3：arr2 的第 2 个数是 0,算一下距离 |3 减 0| = 3。3 比 2 大,这个数离得够远,接着看下一个。
比 arr2[3] = 7 · 距离 4：arr2 的第 3 个数是 7,算一下距离 |3 减 7| = 4。4 比 2 大,这个数离得够远,接着看下一个。
结算 · 3 达标：arr2 整排都看完了,没有任何一个数跟 3 的距离落在 2 以内,所以 3 达标,标绿,计入答案。已确认达标 1 个。
检查 arr1[1] = 4：现在轮到 arr1 的第 1 个数,值是 4。去 arr2 这排里挨个看,有没有哪个数跟它的距离不超过 2。只要找到一个,4 就出局;一个都没有,它才达标。
比 arr2[0] = 9 · 距离 5：arr2 的第 0 个数是 9,算一下距离 |4 减 9| = 5。5 比 2 大,这个数离得够远,接着看下一个。
比 arr2[1] = 8 · 距离 4：arr2 的第 1 个数是 8,算一下距离 |4 减 8| = 4。4 比 2 大,这个数离得够远,接着看下一个。
比 arr2[2] = 0 · 距离 4：arr2 的第 2 个数是 0,算一下距离 |4 减 0| = 4。4 比 2 大,这个数离得够远,接着看下一个。
比 arr2[3] = 7 · 距离 3：arr2 的第 3 个数是 7,算一下距离 |4 减 7| = 3。3 比 2 大,这个数离得够远,接着看下一个。
结算 · 4 达标：arr2 整排都看完了,没有任何一个数跟 4 的距离落在 2 以内,所以 4 达标,标绿,计入答案。已确认达标 2 个。
检查 arr1[2] = 10：现在轮到 arr1 的第 2 个数,值是 10。去 arr2 这排里挨个看,有没有哪个数跟它的距离不超过 2。只要找到一个,10 就出局;一个都没有,它才达标。
比 arr2[0] = 9 · 距离 1：arr2 的第 0 个数是 9,算一下距离 |10 减 9| = 1。1 不超过 2,这就是一个近邻,出局信号亮了,10 注定达不了标。后面几个还是顺手扫完看清楚。
比 arr2[1] = 8 · 距离 2：arr2 的第 1 个数是 8,算一下距离 |10 减 8| = 2。2 不超过 2,这就是一个近邻,出局信号亮了,10 注定达不了标。后面几个还是顺手扫完看清楚。
比 arr2[2] = 0 · 距离 10：arr2 的第 2 个数是 0,算一下距离 |10 减 0| = 10。10 比 2 大,这个数离得够远,接着看下一个。
比 arr2[3] = 7 · 距离 3：arr2 的第 3 个数是 7,算一下距离 |10 减 7| = 3。3 比 2 大,这个数离得够远,接着看下一个。
结算 · 10 出局：这排里出现过距离不超过 2 的数,说明 10 有近邻,不达标,标红,不计入。已确认达标 2 个。
检查 arr1[3] = 7：现在轮到 arr1 的第 3 个数,值是 7。去 arr2 这排里挨个看,有没有哪个数跟它的距离不超过 2。只要找到一个,7 就出局;一个都没有,它才达标。
比 arr2[0] = 9 · 距离 2：arr2 的第 0 个数是 9,算一下距离 |7 减 9| = 2。2 不超过 2,这就是一个近邻,出局信号亮了,7 注定达不了标。后面几个还是顺手扫完看清楚。
比 arr2[1] = 8 · 距离 1：arr2 的第 1 个数是 8,算一下距离 |7 减 8| = 1。1 不超过 2,这就是一个近邻,出局信号亮了,7 注定达不了标。后面几个还是顺手扫完看清楚。
比 arr2[2] = 0 · 距离 7：arr2 的第 2 个数是 0,算一下距离 |7 减 0| = 7。7 比 2 大,这个数离得够远,接着看下一个。
比 arr2[3] = 7 · 距离 0：arr2 的第 3 个数是 7,算一下距离 |7 减 7| = 0。0 不超过 2,这就是一个近邻,出局信号亮了,7 注定达不了标。后面几个还是顺手扫完看清楚。
结算 · 7 出局：这排里出现过距离不超过 2 的数,说明 7 有近邻,不达标,标红,不计入。已确认达标 2 个。
完成 · 距离值 2：arr1 的四个数都查完了。3 和 4 在 arr2 里找不到距离 ≤ 2 的近邻,达标涂绿;10 和 7 都有挨得很近的邻居,出局涂红。所以距离值就是这两个达标的数,答案 2,跟开头说的对上了。
边界:d=0 时只有相等才算近邻;全都找得到近邻则答案 0;只有离群的大数能达标。
面试重点:暴力 O(m·n) 对排序二分 O((m+n)log n);排序后只看第一个不小于 a 减 d 的候选;Java 的 binarySearch 负返回值要还原。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int: arr2.sort() ans = 0 for x in arr1: i = bisect_left(arr2, x - d) ans += i == len(arr2) or arr2[i] > x + d return ans复杂度
- 时间：O((m+n)·log n)，m、n 分别是 arr1、arr2 的长度。参考代码先给 arr2 排序是 O(n log n),再对 arr1 的每个数做一次二分各 O(log n),合起来 m log n,总体 O((m+n)·log n)。动画演示的暴力逐个比对则是 O(m·n),数据小时也够用
- 空间：O(1) 到 O(n)，除排序外只用了计数器等常数个变量。空间按峰值看排序内部开销:不计排序记 O(1);要计的话,C++ 与 Java 的排序是 O(log n) 递归栈,Python 的 list.sort 最坏 O(n)
易错点
面试追问把动画讲成自己的话
追问暴力法和排序加二分的复杂度差在哪,什么时候值得排序?
追问为什么排序后只要检查第一个不小于 a 减 d 的数就够了?
追问Java 用 Arrays.binarySearch 要注意什么?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
找出数组排序后的目标下标
LeetCode 2089 · 简单 · 沿着 二分套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题