題目描述
整數(shù)數(shù)組中找出一組和為目標值的兩個整數(shù)（不能重復利用這個數(shù)組中同樣的元素），并返回他們的數(shù)組下標楚里。
示例：
輸入：[2, 7, 11, 15] 和 9
原因：nums[0] + nums[1] = 2 + 7 = 9
輸出：[0, 1]
解析
考察重點：應用HashMap存儲數(shù)據(jù)并快速檢索断部，空間換取時間
實現(xiàn)方法：
很明顯暴力法可以兩次循環(huán)遍歷，對數(shù)組中的每一個整數(shù)都去查找是否有匹配的結(jié)果班缎，此時實際復雜度為O(n^2)蝴光。在這里我們應用HashMap存儲已經(jīng)遍歷過的整數(shù)。當讀取一個整數(shù)時去HashMap中查找是否有匹配的結(jié)果达址，如果存在返回結(jié)果蔑祟，如果不存在將當前整數(shù)存入HashMap中，直到遍歷完數(shù)組中全部整數(shù)為止沉唠。每次讀取整數(shù)都會檢查它之前讀入的整數(shù)是否有匹配的結(jié)果疆虚，這樣當遍歷了全部數(shù)組整數(shù)之后，就會檢查了所有可能的結(jié)果满葛。使用HashMap存儲記錄是一種典型的用空間換取時間的做法径簿，時間復雜度為O(n)，空間復雜度為O(n)嘀韧。
代碼
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for(int i = 0; i < nums.length; ++i){
Integer j;
if((j = map.get(target - nums[i])) != null){//如果存在匹配結(jié)果篇亭，返回
return new int[]{i,j};
}
map.put(nums[i], i);//放入HashMap中存儲，繼續(xù)遍歷數(shù)組
}
return null;
}
