s*******h
发帖数: 86 | 1 面试码工，当场问一个算法问题，我回答的糊里糊涂。请教这里的大拿们。
问题：一个数组，都是随机的整数。要求写程序，对应一个目标整数，如果这个数组里
有两个数的和，等于这个目标整数，那么就返回真，否则假。
bool ExistTwoNumbersSum (int[] numberArray, int target)
例如：numberArray: 1,6,5,7,8,32,21。
target: 26,
return true (5+21=26)
如果target: 100, return false. 因为找不到两个数之和等于100.
------------------------------------
我想，肯定不能简单的从头一个一个比较，那太没效率了，查找长度是n的平方？有效
率的方法是二分查找，但是需要先排序，平均最快的是快速排序，查找长度也有NlogN,
加上二分查找，又需要logN。所以总的查找长度是（N+1)logN ?
对不对啊? 有没有更好的方法啊？最好写出伪码。谢谢！ | z****e
发帖数: 54598 | 2 two sum
leetcode的第一题
先sort
然后一个从前一个从后开始扫
如果之和大于目标值，前指针往后走一格
如果之和小于目标值，后指针往前走一格
这种题目不会实在是不应该
烂大街的题了 | B****S
发帖数: 597 | 3 sliding window: like the one used in package trasmission in networks
【在 s*******h 的大作中提到】
: 面试码工，当场问一个算法问题，我回答的糊里糊涂。请教这里的大拿们。
: 问题：一个数组，都是随机的整数。要求写程序，对应一个目标整数，如果这个数组里
: 有两个数的和，等于这个目标整数，那么就返回真，否则假。
: bool ExistTwoNumbersSum (int[] numberArray, int target)
: 例如：numberArray: 1,6,5,7,8,32,21。
: target: 26,
: return true (5+21=26)
: 如果target: 100, return false. 因为找不到两个数之和等于100.
: ------------------------------------
: 我想，肯定不能简单的从头一个一个比较，那太没效率了，查找长度是n的平方？有效
| k**********g
发帖数: 989 | 4
Another solution is to use hashtable and scan. For each new incoming value,
check if its complement = (expected sum minus incoming value) already exists
in the hashtable. If so, finish. If not, add incoming value to hashtable.
Since there's no information on the range, magnitude or number of elements
in input data, the complexity may depend on the choice of hashtable
implementation (re: collision and table growth etc), but can be expected to
do better than Log N.
【在 z****e 的大作中提到】
: two sum
: leetcode的第一题
: 先sort
: 然后一个从前一个从后开始扫
: 如果之和大于目标值，前指针往后走一格
: 如果之和小于目标值，后指针往前走一格
: 这种题目不会实在是不应该
: 烂大街的题了
| s*w
发帖数: 729 | 5 大拿笔误了，两个 if 的 execution 要换一下
【在 z****e 的大作中提到】
: two sum
: leetcode的第一题
: 先sort
: 然后一个从前一个从后开始扫
: 如果之和大于目标值，前指针往后走一格
: 如果之和小于目标值，后指针往前走一格
: 这种题目不会实在是不应该
: 烂大街的题了
| N********n
发帖数: 8363 | 6 Classic O(N) hashtable problem. Put every # in a hashtable then for
each # check if "sum - #" is in the hashtable.
Make sure you handle the case where # == sum - #. | c********p
发帖数: 1969 | 7 赵老师别打击人呀。。。
【在 z****e 的大作中提到】
: two sum
: leetcode的第一题
: 先sort
: 然后一个从前一个从后开始扫
: 如果之和大于目标值，前指针往后走一格
: 如果之和小于目标值，后指针往前走一格
: 这种题目不会实在是不应该
: 烂大街的题了
| w**z
发帖数: 8232 | 8 这是最简单的入门题。建议你多去jobhunting 版， 这里不适合讨论面试题。
【在 s*******h 的大作中提到】
: 面试码工，当场问一个算法问题，我回答的糊里糊涂。请教这里的大拿们。
: 问题：一个数组，都是随机的整数。要求写程序，对应一个目标整数，如果这个数组里
: 有两个数的和，等于这个目标整数，那么就返回真，否则假。
: bool ExistTwoNumbersSum (int[] numberArray, int target)
: 例如：numberArray: 1,6,5,7,8,32,21。
: target: 26,
: return true (5+21=26)
: 如果target: 100, return false. 因为找不到两个数之和等于100.
: ------------------------------------
: 我想，肯定不能简单的从头一个一个比较，那太没效率了，查找长度是n的平方？有效
|
|
