題目
給定一個(gè)整數(shù)數(shù)組 nums 和一個(gè)目標(biāo)值 target粒氧，請(qǐng)你在該數(shù)組中找出和為目標(biāo)值的那 兩個(gè) 整數(shù)，并返回他們的數(shù)組下標(biāo)。
你可以假設(shè)每種輸入只會(huì)對(duì)應(yīng)一個(gè)答案型宝。但是，你不能重復(fù)利用這個(gè)數(shù)組中同樣的元素絮爷。
示例:
給定 nums = [2, 7, 11, 15], target = 9
因?yàn)?nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
思路
- 暴力解法
循環(huán)遍歷兩次數(shù)組
時(shí)間復(fù)雜度O(n^2) 空間復(fù)雜度O(1) - 利用HashMap
遍歷數(shù)組趴酣，將Key=數(shù)值，Value=索引值存入HashMap坑夯，
依次對(duì)數(shù)組中的值a岖寞，計(jì)算targrt-a，在HashMap中查找是否存在a柜蜈。
注意：數(shù)組存入HashMap會(huì)存在一個(gè)小細(xì)節(jié)：數(shù)組中若存在重復(fù)的值仗谆，Key會(huì)被覆蓋淑履，只保留最后一個(gè)。 - 在思路2的基礎(chǔ)上鳖谈，對(duì)數(shù)組中的每個(gè)值a岁疼，在插入HashMap前，首先判斷下target-a是否已經(jīng)存在在HashMap中：如果存在則此時(shí)找到一個(gè)解瑰排，直接return就可以了；如果不存在再插入HashMap中暖侨。
Java實(shí)現(xià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;
}
