两数之和(Two-Sum)二分查找解法LeetCode运行报错相关疑问

报错原因分析 #

• 你调用的STL函数binary_search、lower_bound的运行前提是操作的区间为升序排序状态，但LeetCode通用两数之和题目的输入数组是未排序的。你本地测试用的[2,7,11,15]刚好是有序数组，所以运行正常，提交后遇到无序测试用例时，两个函数会触发未定义行为，你遇到的空指针引用就是非法内存访问的典型表现。
• 请检查封装函数的返回逻辑：题目要求无论是否找到结果都要返回合法的vector<int>对象，如果你仅在找到匹配对的分支写了return语句，未匹配的分支没有返回值，也会触发运行时错误。
• 另外如果没有提前处理输入数组长度小于2的边界情况，循环逻辑也可能出现迭代器越界问题。

二分查找思路很少用于求解两数之和的原因 #

• 时间复杂度更高：如果要适配通用无序数组的场景，需要先对数组做排序，排序本身的时间复杂度为O(nlogn)，加上遍历+二分查找的O(nlogn)，总时间复杂度为O(nlogn)，远高于主流哈希表解法的O(n)。
• 实现成本更高：排序会打乱原数组的下标，你需要额外存储每个元素对应的原始下标，代码复杂度比直接用哈希表存储「值-下标」映射高很多，出错概率也更大。
• 适用场景有限：只有当题目明确给出输入数组已排序的前提时（比如LeetCode第167题两数之和II），二分或者双指针才是更优的解法，通用场景下二分思路没有任何优势。

二分思路的正确实现方式（仅作参考） #

如果一定要用二分思路实现通用两数之和，可按如下逻辑修改：

1. 构造pair数组，每个元素存储(原数组值, 原始下标)
2. 对pair数组按值升序排序
3. 遍历每个元素，在当前元素之后的区间二分查找target - 当前值，匹配成功则返回两者的原始下标即可

内容的提问来源于stack exchange，提问作者Soham Mafidar