最近開始刷了點(diǎn)LeetCode耸黑，算法的第一個題是Two Sum，看起來很簡單吧零蓉？
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
于是我的解法也很簡單暴力
public class Solution {
public int[] twoSum(int[] nums, int target) {
int[] result = new int[2];
for (int i = 0; i < nums.length; i++) {
int a = nums[i];
for (int j = i + 1; j < nums.length; j++) {
int b = nums[j];
if (a + b == target) {
result[0] = i;
result[1] = j;
}
}
}
return result;
}
}
這種方法嵌套兩層循環(huán)笤受，時間復(fù)雜度分別是O(n)，于是總的時間復(fù)雜度是O(n^2)敌蜂。
打開Editorial Solution發(fā)現(xiàn)了這種時間復(fù)雜度是O(n)箩兽，空間復(fù)雜度增加到O(n)的解法。
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
map.put(nums[i], i);
}
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement) && map.get(complement) != i) {
return new int[] { i, map.get(complement) };
}
}
throw new IllegalArgumentException("No two sum solution");
}
咦紊册？時間復(fù)雜度為什么是O(n)比肄？是時候來看看HashMap源碼了。
先用查找找到containsKey(Object key)方法囊陡。
/**
* Returns <tt>true</tt> if this map contains a mapping for the
* specified key.
*
* @param key The key whose presence in this map is to be tested
* @return <tt>true</tt> if this map contains a mapping for the specified
* key.
*/
public boolean containsKey(Object key) {
return getNode(hash(key), key) != null;
}
containsKey方法調(diào)用了getNode(hash(key), key)方法芳绩，若結(jié)果非null則返回true，否則返回false撞反。所以getNode(hash(key), key)方法就是問題的關(guān)鍵妥色。
/**
* Implements Map.get and related methods
*
* @param hash hash for key
* @param key the key
* @return the node, or null if none
*/
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
這個代碼初看有點(diǎn)復(fù)雜，理解原理的關(guān)鍵點(diǎn)在于
- 返回值
Node<K, V>是什么 - 代碼第三行
tab = table中的table是什么
/**
* Basic hash bin node, used for most entries. (See below for
* TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
*/
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
可見遏片，Node<K, V>是一個存放有Key和Value的鏈表節(jié)點(diǎn)嘹害。
/**
* The table, initialized on first use, and resized as
* necessary. When allocated, length is always a power of two.
* (We also tolerate length zero in some operations to allow
* bootstrapping mechanics that are currently not needed.)
*/
transient Node<K,V>[] table;
table是Node<K, V>數(shù)組，這里的Node<K, V>則是某一hash值鏈表的頭節(jié)點(diǎn)（不同key的hash值可能重復(fù)吮便，將會被存放在后續(xù)的節(jié)點(diǎn)中）笔呀。值得注意的是，數(shù)組table的長度是2的倍數(shù)髓需。
現(xiàn)在回到getNode(hash(key), key)方法中许师。先看代碼第五行
first = tab[(n - 1) & hash]
沒錯，我們發(fā)現(xiàn)了一個大冪冪僚匆，key對應(yīng)的頭節(jié)點(diǎn)在數(shù)組table中的存放位置微渠，也就是下標(biāo)是(n - 1) & hash這個位運(yùn)算的結(jié)果。n是table的長度（必為2的倍數(shù)）咧擂，則n - 1就是table下標(biāo)的取值范圍逞盆，用二進(jìn)制表示是1111...，共log(n)個1松申。因此(n - 1) & hash實(shí)際上是取了hash二進(jìn)制形式的后n位數(shù)云芦，正好能對應(yīng)數(shù)組table的下標(biāo)俯逾。
數(shù)組通過下標(biāo)訪問Node<K, V>的時間復(fù)雜度是O(1)，而Node<K, V>訪問字段的時間復(fù)雜度也是O(1)焕数，如果頭節(jié)點(diǎn)后沒有節(jié)點(diǎn)纱昧，時間復(fù)雜度就是O(1)。
頭節(jié)點(diǎn)后存在節(jié)點(diǎn)時堡赔，則按下面的代碼遍歷這些節(jié)點(diǎn)识脆，時間復(fù)雜度大于O(1)。
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
至于如何盡量避免產(chǎn)生相同的位運(yùn)算值善已，那就是hash算法的事了灼捂，不在本文討論范圍內(nèi)。實(shí)際上一個好的hash算法是可以讓平均時間復(fù)雜度為O(1)的换团。
至此悉稠，containsKey(Object key)方法的時間復(fù)雜度問題就基本解決了。
寫完這篇文章我就發(fā)現(xiàn)啊艘包，原來LeetCode最簡單的Two Sum也能學(xué)到這么多東西的猛，還是好好去刷LeetCode吧。
