12 | 面试实战：经典排序算法面试题详解

两个数组的交集，可以使用hash table，把一个数组存入到hash table，然后遍历另外一个数组 杨氏矩阵可以采用二分法优化。

2-sum问题，排序后数组索引值就变了，对于返回原数组的索引值可能并不适用。

2-sum的数组无序这部分排序的影响点没列出来？我的理解是最后基本等效于排序的复杂度？？因为后续单如果是头尾遍历的复杂度就是O(n)了，所以取排序的复杂度？

开始想的杨氏矩阵采用二分法是有问题的。我又思考了下，可以采用分治法，比如把4x4的矩阵分解为4个2x2矩阵，每个子矩阵的左上角是最小值，右下角是最大值，然后可以快速判断目标值在哪几个子矩阵里，然后递归求解。请问老师，不知道还有木有其它解法呢？

2-sum问题，遍历一次数据，把小于目标的元素存入hashmap(键值对)， 元素值做为key，数组下标做为value， 遍历得到的hashmap， 判断当前key 和 目标值-key对应的元素是否都存在，都存在，那么[hashmap.get(key), hashmap.get(目标值-key)] 为符合条件的两个元素下标。 量数据交集问题也可以将较小的数组存入到hash table，然后遍历较大数据在hash table中查找来解决。需要注意的是，当map中查找到对应元素时，需要将元素从hash table中删除，避免重复查询。