三个有序数组找最接近元素：两种解法的差异与复杂度疑问

疑问1：为何第一种解法的时间复杂度为O(p+q+r)，而第二种解法的时间复杂度却是O(NlogN)？ #

你当前提供的解法2代码不完整且逻辑与解法1高度重复，从现有代码来看它的时间复杂度同样是O(p+q+r)，不可能是O(NlogN)。

如果确实存在时间复杂度为O(NlogN)的版本，那应该是另一种实现思路：比如先对其中一个数组排序（时间O(NlogN)），然后遍历另外两个数组的元素组合，对第三个数组用二分查找寻找最接近的元素，此时整体时间复杂度由排序的O(NlogN)主导，或是遍历+二分的O((p+q)logr)（当p/q/r量级接近时等价于O(NlogN)）。你现在贴的解法2代码显然不是这个版本，应该是粘贴错误了。

疑问2：若第二种解法并未采用二分查找的分治逻辑（未进行对半划分），为何称其使用了二分查找？ #

当前你给出的解法2代码完全没有用到二分查找，连最基本的对半划分、折半查找逻辑都不存在。大概率是你混淆了不同版本的实现——真正用到二分查找的版本，核心逻辑应该是：

• 遍历数组A和B的每一对元素(a,b)
• 在数组C中用二分查找找到与(a+b)/2最接近的元素c，计算三者的差值
• 全程记录最小差值对应的三元组
  这种实现才会用到二分查找的分治逻辑，而你现在的代码只是和解法1一样的三指针遍历，和二分完全无关。

疑问3：第二种解法不也是递增最小值所在数组的索引吗？ #

是的，你贴的解法2本质上和解法1做的是同一件事：都是移动当前三个指针指向元素中最小值所在数组的索引。
解法2里的判断条件A[i] == minimum && A[i] <= B[j] && A[i] <= C[k]其实是冗余的——因为A[i] == minimum已经能直接推导A[i] <= B[j]和A[i] <= C[k]，多余的判断完全不改变逻辑，只是写法啰嗦了而已。

内容的提问来源于stack exchange，提问作者MinKwon Kim