LeetCode 新题 Two Sum II 求最佳解

wenqiang88 发表于 2015-1-10 12:16
这个肯定要算的吧...

其实我经常都很不理解，因为实际应用情况下只要做一个table就能一劳永逸，当然我知道其实是偏题了- -因为题目要的是动态输入，但是总是不自觉的香道这个，偶真是太小家子气了...

用hash map呢？

用hash map呢？

c__jay 发表于 2015-1-10 12:41
其实我经常都很不理解，因为实际应用情况下只要做一个table就能一劳永逸，当然我知道其实是偏题了- -因为 ...

没有动态输入吧，就是给你一个array。做table需要额外的空间，但是如果2个指针往中间移的话不需要

c__jay 发表于 2015-1-10 12:41
其实我经常都很不理解，因为实际应用情况下只要做一个table就能一劳永逸，当然我知道其实是偏题了- -因为 ...

没有动态输入吧，就是给你一个array。做table需要额外的空间，但是如果2个指针往中间移的话不需要

到底是怎么解决的呀？

O(n)就最好了.

希望找到两个数加起来=0... 并且我们还有extra information... 负数和正数的分割点在哪里...
那么问题等同于给两个sorted array, 找里面有没有相同的数字(把其中的负数array反过来...)

然后可用adversary argument证明这个要O(n)时间.

我不是很懂map的工作原理。但是这题用map来做，就是把index和value 来map起来，利用map的查找时间可以达到o(n)的时间对吧。如果这样的话，可不可以用二分法查找结合map的查找时间来完成呢？这只是一个大体思路。