作個人記錄LeetCode解題過程中的一些啟發之用。
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.
給出一個int型數組，和一個目標（和）target，返回數組中和為target的兩int型數組元素的下標 實現上述功能。 Example：
Given nums = [2, 7, 11, 15], target = 9,Because nums[0] + nums[1] = 2 + 7 = 9,return [0, 1].這是一個很簡單的題目,很容易實現，不過算法的時間復雜度值得考究。 開始隨手寫的方法如下，java實現：
public class Solution { public int[] twoSum(int[] nums, int target) { int[] a = new int[2]; for(int i = 0; i < nums.length; i++){ for(int j = i+1; j<nums.length; j++){ if(nums[j] == target - nums[i]){ a[0]=i; a[1]=j; } } } return a; }}上面的算法時間復雜度為O(n2)，雖然accepted,顯然不理想
得票數第一的Java實現，時間復雜度為O(n):
public int[] twoSum(int[] numbers, int target) { int[] result = new int[2]; Map<Integer, Integer> map = new HashMap<Integer, Integer>(); for (int i = 0; i < numbers.length; i++) { if (map.containsKey(target - numbers[i])) { result[1] = i + 1; result[0] = map.get(target - numbers[i]); return result; } map.put(numbers[i], i + 1); } return result;}這里用了HashMap數據結構，Java中HashMap的containsKey、get、put方法時間復雜度為O(1)（在HashMap中的存儲的entry對的Key的哈希不相等時，即不發生碰撞情況）
與上面第一種算法的兩層for循環相比，這種算法只需要遍歷nums[]數組一次，將其以（nums[] , index）鍵值對存進HashMap。并且是先移動下標i，再判斷containsKey()，再將其put進HashMap，再移動下標，在前面生成的HashMap中進行containsKey判斷。
這種在靠后點判斷之前點的方法與第一種暴力檢索的在靠前點遍歷之后點的思路是完全相反的，這也是由HashMap的通過hashcode()來search的性質決定的，對于nums[]規模較大時，HashMap的效率要遠優于兩層遍歷方法。
同樣時間復雜度為O(n)，這里采用的是python里的dict字典數據結構。遍歷nums[]，先判斷nums[i],再將target-nums[i]存進dict，直到在nums[]中遍歷到在dict中存儲過的元素。
HashMap 是一個散列表，它存儲的內容是鍵值對(key-value)映射。HashMap 繼承于AbstractMap，實現了Map、Cloneable、java.io.Serializable接口。HashMap 的實現不是同步的，這意味著它不是線程安全的。它的key、value都可以為null。此外，HashMap中的映射不是有序的。HashMap 的實例有兩個參數影響其性能：“初始容量” 和 “加載因子”。容量 是哈希表中桶的數量，初始容量 只是哈希表在創建時的容量。加載因子 是哈希表在其容量自動增加之前可以達到多滿的一種尺度。當哈希表中的條目數超出了加載因子與當前容量的乘積時，則要對該哈希表進行 rehash 操作（即重建內部數據結構），從而哈希表將具有大約兩倍的桶數。 
新聞熱點
疑難解答
