P3003. 两数之和绝对值最小

解题思路

注意，本题和 两数之和 II - 输入有序数组 解题方法非常类似。但在判断指针移动的条件上，稍微有些不同。

排序与双指针

要用上 相向双指针，首先要对 lst 数组进行排序。

两个数的和的 绝对值越小，说明这两个数的和越接近于 0。所以这道题可以换一种问法：找到两个数使得它们的和尽可能地接近 0。我们可以使用相向双指针 left 和 right 指向一小一大两个数，当：

• lst[left] + lst[right] > 0 时，如果令 left 右移，两数和会进一步增大，距离 0 更远，因此需要令 right 左移。
• lst[left] + lst[right] < 0 时，如果令 right 左移，两数和会进一步减小，距离 0 更远，因此需要令 left 右移。
• lst[left] + lst[right] == 0 时，两数和的绝对值已经达到最小，可以直接退出循环。

另外，对于每对两数和 sum2 = lst[left] + lst[right]，我们都应该令其绝对值与之前的得到最小两数和绝对值进行比较并更新。上述思路整理为代码即：

另一种移动策略

如果没有想到上述方法，在选择 left 和 right 移动哪一个的问题上，我们也可以直接考虑移动后的结果。当：

• abs(lst[left+1] + lst[right]) < abs(lst[left] + lst[right-1])，即 left 右移后两数和的绝对值小于 right 左移的结果，那么我们令 left 右移。
• abs(lst[left+1] + lst[right]) >= abs(lst[left] + lst[right-1])，即 left 右移后两数和的绝对值大于等于 right 左移的结果，那么我们令 right 左移。

上述思路整理为代码即：

代码

解法一

将题目转化为考虑最接近 target = 0 的两数和。

复杂度分析 设输入数组的长度为 n。

• 读入与解析：逐段切出 n 个整数，属于线性扫描量级。
• 排序 lst.sort(null)：O(n log n)，这是整个算法的瓶颈。
• 相向双指针扫描：每一轮循环中 left 与 right 至少有一个移动一步，两个指针相向而行合计至多移动 n 步，因此这一段是 O(n)；每轮内部只有求和、取绝对值和比较更新答案这几个常数操作。

总时间复杂度为 O(n log n)，由排序主导；空间复杂度为 O(n)，用于存放解析后的数字列表（排序在列表上原地进行，额外空间只有常数个变量和长度为 3 的答案列表）。