英文題目：
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.
中文題目：
給定一個(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ù)組中同樣的元素。
public class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> m = new HashMap<Integer, Integer>();
int[] res = new int[2];
for(int i = 0;i < nums.length;++i){
m.put(nums[i],i);
}
for(int i = 0;i < nums.length;++i){
int t = target - nums[i];
if(m.containsKey(t) && m.get(t) != i){
res[0] = i;
res[1] = m.get(t);
break;
}
}
return res;
}
}
這道題首先想到的就是暴力搜索袖迎，但是由于暴力搜索的方法是遍歷所有的兩個(gè)數(shù)字的組合，然后算其和腺晾，這樣雖然節(jié)省了空間燕锥，但是時(shí)間復(fù)雜度高。暴力搜索的時(shí)間復(fù)雜度是 O(n^2)悯蝉。那么只能想個(gè) O(n) 的算法來(lái)實(shí)現(xiàn)归形，一般來(lái)說(shuō)，提高時(shí)間復(fù)雜度需要用空間來(lái)?yè)Q鼻由，但這里只想用線性的時(shí)間復(fù)雜度來(lái)解決問(wèn)題暇榴，就是說(shuō)只能遍歷一個(gè)數(shù)字，另一個(gè)數(shù)字可以事先將其存儲(chǔ)起來(lái)蕉世，使用一個(gè) HashMap蔼紧，來(lái)建立數(shù)字和其坐標(biāo)位置之間的映射，由于 HashMap 是常數(shù)級(jí)的查找效率狠轻，這樣在遍歷數(shù)組的時(shí)候奸例，用 target 減去遍歷到的數(shù)字，就是另一個(gè)需要的數(shù)字了向楼，直接在 HashMap 中查找其是否存在即可查吊，注意要判斷查找到的數(shù)字不是第一個(gè)數(shù)字，比如 target 是4湖蜕，遍歷到了一個(gè)2逻卖，那么另外一個(gè)2不能是之前那個(gè)2，整個(gè)實(shí)現(xiàn)步驟為：先遍歷一遍數(shù)組昭抒，建立 HashMap 映射评也，然后再遍歷一遍虚茶，開(kāi)始查找，找到則記錄 index仇参。
(Java)第二種解法：
public class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> m = new HashMap<Integer, Integer>();
int[] res = new int[2];
for (int i = 0; i < nums.length; ++i) {
if (m.containsKey(target - nums[i])) {
res[0] = i;
res[1] = m.get(target - nums[i]);
break;
}
m.put(nums[i], i);
}
return res;
}
}
