返回信息流这是leetcode中的一道简单题。。。题目如下。
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
然而我的问题如下：
大部分人首先会想到两个for循环解决问题。这样时间复杂度为O(n^2)。
我看网上呢有一种解法：使用Hashtable去get key值。这样就可以将时间复杂度降为O(n)。利用的是Hashtable中查找元素的时间为常数。然而我查看Hashtable中get()方法的源码，每调用一次get()方法，都会调用for循环遍历一次。这样当两次调用get()方法，岂不是反而增加时间复杂度？如果没有增加时间复杂度，那么为何get()方法耗费的时间不包含在内？
```
//网上的解法
import java.util.Hashtable;
public class Solution {
public int[] twoSum(int[] nums, int target) {
int[] tmp = new int[2];
Hashtable<Integer, Integer> table = new Hashtable<Integer, Integer>();
for(int i = 0; i < nums.length; i++){
Integer n = table.get(nums[i]);
if(n == null) table.put(nums[i], i);
n = table.get(target - nums[i]);
if(n != null && n < i){
tmp[0] = i;
tmp[1] = n;
break;
}
}
return tmp;
}
}
//---------------------------------
//get()方法的源码
public synchronized V get(Object key) {
Entry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
return (V)e.value;
}
}
return null;
}
```
这是一条镜像帖。来源：北邮人论坛 / java / #53420同步于 2016/10/7
该镜像源已超过 30 天没有更新，可能在源站已被删除。
Java机器人发帖
two sum 问题
yohu
2016/10/7镜像同步8 回复
订阅后，新回复会通过你的通知中心匿名送达。
8 条回复
HashTable和HashMap就是一个散列表，计算散列位置的复杂度是O(1)
源码里的for循环是在遍历该散列位置的所有冲突的元素链表，有冲突的话时间复杂度会略高，但是也没到O(n)
多谢大神~
【 在 dss886 的大作中提到: 】
: HashTable和HashMap就是一个散列表，计算散列位置的复杂度是O(1)
: 源码里的for循环是在遍历该散列位置的所有冲突的元素链表，有冲突的话时间复杂度会略高，但是也没到O(n)
真正的查找算法是那个不起眼的“e = tab[index]”。然后，那个for循环只是为了解决极少会出现的冲突而放置的。
【 在 yohu 的大作中提到: 】
: 这是leetcode中的一道简单题。。。题目如下。
: Given nums = [2, 7, 11, 15], target = 9,
: Because nums[0] + nums[1] = 2 + 7 = 9,
: ...................
多谢暖神~
【 在 nuanyangyang 的大作中提到: 】
: 真正的查找算法是那个不起眼的“e = tab[index]”。然后，那个for循环只是为了解决极少会出现的冲突而放置的。
: