慢慢開始刷leetcode扮授。
自勉穴肘。
public int[] twoSum(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (target - nums[i] == nums[j])
return new int [] {i, j};
}
}
return null;
}
暴力搜索 殘差
時(shí)間復(fù)雜度O(n**2)
空間復(fù)雜度O(1)
另外兩種以HashMap為主
總結(jié)下hashmap的特點(diǎn)
HashMap<String, Double> map = new HashMap<String, Double>();
map.put("ss", 11.0);
每個(gè)java object 都有hashCode() 方法。
put 源碼
public V put(K key, V value)
{
// 如果 key 為 null杖们，調(diào)用 putForNullKey 方法進(jìn)行處理
if (key == null)
return putForNullKey(value);
// 根據(jù) key 的 keyCode 計(jì)算 Hash 值
int hash = hash(key.hashCode());
// 搜索指定 hash 值在對(duì)應(yīng) table 中的索引
int i = indexFor(hash, table.length);
// 如果 i 索引處的 Entry 不為 null，通過循環(huán)不斷遍歷 e 元素的下一個(gè)元素
for (Entry<K,V> e = table[i]; e != null; e = e.next)
{
Object k;
// 找到指定 key 與需要放入的 key 相等（hash 值相同
// 通過 equals 比較放回 true）
if (e.hash == hash && ((k = e.key) == key
|| key.equals(k)))
{
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
// 如果 i 索引處的 Entry 為 null，表明此處還沒有 Entry
modCount++;
// 將 key辛块、value 添加到 i 索引處
addEntry(hash, key, value, i);
return null;
}
方法中Map.Entry接口也是key-value對(duì)， HashMap中完全沒有考慮value铅碍，只由key的HashCode決定存儲(chǔ)位置润绵，再一起存儲(chǔ)value。
indexFor 則搜索table處的索引胞谈。
static int indexFor(int h, int length)
{
return h & (length-1);
}
當(dāng) length 總是 2 的倍數(shù)時(shí)尘盼，h & (length-1) 將是一個(gè)非常巧妙的設(shè)計(jì)：假設(shè) h=5,length=16, 那么 h & length - 1 將得到 5憨愉；如果 h=6,length=16, 那么 h & length - 1 將得到 6 ……如果 h=15,length=16, 那么 h & length - 1 將得到 15；但是當(dāng) h=16 時(shí) , length=16 時(shí)卿捎，那么 h & length - 1 將得到 0 了配紫；當(dāng) h=17 時(shí) , length=16 時(shí)，那么 h & length - 1 將得到 1 了……這樣保證計(jì)算得到的索引值總是位于 table 數(shù)組的索引之內(nèi)午阵。
兩步hash法
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i = 0; i < nums.length; i++) {
map.put(nums[i], i);
}
for (int i = 0; i < nums.length; i++) {
int res = target - nums[i];
if (map.containsKey(res) && (map.get(res) != i)) {
return new int[] {i, map.get(res)};
}
}
return null;
}
先將value-key存入map躺孝，再索引。
Time complexity : O(n). We traverse the list containing n elements exactly twice. Since the hash table reduces the look up time to O(1), the time complexity is O(n).
Space complexity : O(n). The extra space required depends on the number of items stored in the hash table, which stores exactly n elements.
一步法
在存入map時(shí)就檢索是否存在.
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i = 0; i < nums.length; i++) {
int res = target - nums[i];
if (map.containsKey(res)) {
return new int[] {map.get(res), i};
}
map.put(nums[i], i);
}
return null;
}
