面试题杂谈：体重和

有n个人，要确定存不存在这样两个人，其体重和是112公斤， 能否找到一个O（N）的算法来解决此问题？有的话，说明算法是什么？ 没有的话，说明原因，及最好的时间复杂度是多少？

现在大公司面试越来越多的考虑到算法方面的东西了，可能是对于产品来说一般技术壁垒太小了，核心就是比用户的忠诚度与产品的性能，而很多时候，性能与算法关系密切。

初看这题，一下子就能想到的就是对于每个人A，找一个B，B的体重是112-A就行了，这样复杂度是O（n^2)。

另一个解决方案是从找112-A这个地方来优化了，因为我们知道了A体重，有一个数组里找112-A可以二分查找，但二分查找要求有序，而排序复杂度可以为O（nlogn)，这样查找的复杂度也是O(nlogn)，总体复杂度还是O(nlogn)，比上一个算法要好些。

还有没有更好的办法呢？对就是hash，对于hash来说查找一个元素为O（1）,所以整体复杂度就是O（N）了。hash是个好办法，但是一下子要想到点上也不容易，如果题中说了体重是整数的话，那么很容易想到就是hash了，开一个112的数组，有体重在相应位置的人数加1即可，再枚举A体重，查找B体重。

所以觉得有时候就是这样，一个方法可以，换点东西其实用相同方法也可以，但是就是不能一下子想到点上。不知道还有没有其它更好的解决方案。