1. 题目
给定两个整数数组a和b，计算具有最小差绝对值的一对数值（每个数组中取一个值），并返回该对数值的差
示例：
输入：{1, 3, 15, 11, 2}, {23, 127, 235, 19, 8}
输出： 3，即数值对(11, 8)
提示：
1 <= a.length, b.length <= 100000
-2147483648 <= a[i], b[i] <= 2147483647
正确结果在区间[-2147483648, 2147483647]内
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/smallest-diffe
【题目解析】
本题是来自LeetCode的一道面试题，编号为16.06，中文名为"最小差（排序+双指针）"。题目要求我们从两个给定的整数数组`a`和`b`中找到一对数值，使得它们的差的绝对值最小，并返回这个差值。数组`a`和`b`的长度均不超过100000，且数组中的元素在`[-2147483648, 2147483647]`的范围内。正确答案也在此范围内。
【解题策略】
解决此问题的关键在于有效利用排序和双指针技术。以下是解题步骤：
1. **排序**：首先对两个数组`a`和`b`进行升序排序，这是为了方便后续比较两个数组中的元素。
2. **初始化**：设置两个指针`i`和`j`分别指向`a`和`b`的起始位置，以及一个变量`mindis`用来存储当前找到的最小差值，初始值设为`INT_MAX`，表示整数最大值。
3. **遍历**：使用循环结构，当`i`小于`a`的长度且`j`小于`b`的长度时，进行以下操作：
- 计算差值`diff`：`a[i]`减去`b[j]`。
- 检查差值是否越界，如果`diff`小于`INT_MIN`，则需要更新`mindis`，确保结果在合法范围内。
- 判断`diff`的正负，如果`a[i]`小于等于`b[j]`，则将`i`指针向后移动一位，因为我们要找的是差值最小，所以当`a`的元素小于等于`b`的元素时，我们希望`a`的元素变大来减小差值；反之，如果`b[j]`小于`a[i]`，则将`j`指针向后移动一位。
4. **返回结果**：遍历结束后，`mindis`存储的就是最小差值，返回即可。
【代码实现】
```cpp
class Solution {
public:
int smallestDifference(vector<int>& a, vector<int>& b) {
sort(a.begin(), a.end()); // 对数组a进行排序
sort(b.begin(), b.end()); // 对数组b进行排序
if (a.back() <= b.front()) // 特殊情况处理，a的最大值小于等于b的最小值
return b.front() - a.back();
if (b.back() <= a.front()) // 特殊情况处理，b的最大值小于等于a的最小值
return a.front() - b.back();
int i = 0, j = 0, na = a.size(), nb = b.size(), mindis = INT_MAX;
long diff;
while (i < na && j < nb) {
diff = a[i] - b[j];
if (diff < INT_MIN)
mindis = min(mindis, abs((int)diff)); // 更新最小差值
if (a[i] <= b[j])
i++; // a小，a往后走
else
j++; // b小，b往后走
}
return mindis;
}
};
```
【复杂度分析】
- 时间复杂度：O(n log n)，其中n是数组的总长度。排序操作的时间复杂度为O(n log n)，双指针遍历的时间复杂度为O(n)。
- 空间复杂度：O(1)。除了输入数组外，没有额外的空间开销。
通过上述策略，我们可以高效地解决这道面试题，找到两个数组中最小差值的一对数值。这种解法展示了在处理数组问题时，排序和双指针是常用且有效的工具，能够帮助我们快速找到解决方案。
