今天去面试被问到一个关于时间复杂的问题，具体情况是，叫我写一个方法，比较易哥数组里任意两个值的和等于一个整数，有的话返回T，没有返回F，我用了双重FOR循环，实现，时间复杂度是 o(n^2)，但是面试的哥哥说，有待改进，我又用对他进行排序后，进行2分查找，时间复杂度是0(n*logn)，但是他又说了，可以用种方法可以把时间复杂度降低到O(N),我实在是想不出了啊，各位大牛，有什么好方法吗？不考虑空间复杂度的情况下。顺带说下，我面试的公司是 无觅网 就单纯的讲他们网站还是很有前途的。大家有兴趣可以去看下PS;不是广告。
问题补充
diaodou 写道
如果已经排好序，可以左右两端同时扫描啊
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--;
}
大体上这个思路吧
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) 可以用其他数据存储结构吧。
