今天去面试被问到一个关于时间复杂的问题，具体情况是，叫我写一个方法，比较易哥数组里任意两个值的和等于一个整数，有的话返回T，没有返回F，我用了双重FOR循环，实现，时间复杂度是 o(n^2)，但是面试的哥哥说，有待改进，我又用对他进行排序后，进行2分查找，时间复杂度是0(n*logn)，但是他又说了，可以用种方法可以把时间复杂度降低到O(N),我实在是想不出了啊，各位大牛，有什么好方法吗？不考虑空间复杂度的情况下。顺带说下，我面试的公司是 无觅网 就单纯的讲他们网站还是很有前途的。大家有兴趣可以去看下PS;不是广告。
问题补充
那你把小于n/2的放到hashmap里面，然后遍历数组，大于n/2的就看看n-x在不在hashmap里面。
但是hashmap的查找平均时间是O(1)，最坏情况仍然是O(N)。
除非有个很好的hash函数，咔咔
或者是先分段，决定可能的段，再进行判断。
如果已经排好序，可以左右两端同时扫描啊
int i = 0, j = nums.length - 1;
while (i < j) {
int rest = n - nums[j];
while (nums[i] < rest) i++;
if (nums[i] == rest) break; // found i, j
else j--;
}
大体上这个思路吧
时间复杂度是一个复合的值,不知道楼主或者面试者排序的时候复杂度考虑了没有?
能到O(N)?
不考虑其中一个是负数的情况？
时间复杂度：O(n)
①排序（升序/降序）
②遍历2min到2max之间的值，如果相等返回T，否则返回F。