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.
題目大意：給定一個整數(shù)數(shù)組峡继，返回兩個數(shù)字的索引雹仿，使它們加起來成為一個特定的目標私恬。
可以假定每個輸入只有一個解決方案柜裸，并且不能使用同一個元素兩次。
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
咋眼一看題目味滞，就感覺可以用暴力搜索樱蛤，這個算法的時間復(fù)雜度是O(n^2)。
暴力法：
class Solution {
public int[] twoSum(int[] nums, int target) {
int length = nums.length;
int index1 = 0;
int index2 = 0;
for(int i=0; i<length; i++){
for(int j=i+1; j<length; j++){
if(nums[i] + nums[j] == target){
index1 = i;
index2 = j;
}
}
}
int[] array = new int[]{index1, index2};
return array;
}
}
由于暴力搜索的方法是遍歷所有的兩個數(shù)字的組合剑鞍，然后算它們的和昨凡，這樣雖然節(jié)省了空間，但是時間復(fù)雜度高蚁署。一般來說便脊，我們?yōu)榱颂岣邥r間的復(fù)雜度，需要用空間來換光戈，如果我們只想用線性的時間復(fù)雜度來解決問題哪痰，那么就是說只能遍歷一個數(shù)字，那么另一個數(shù)字呢久妆，我們可以事先將其存儲起來晌杰，使用一個 HashMap，來建立數(shù)字和其坐標位置之間的映射筷弦，我們都知道 HashMap 是常數(shù)級的查找效率肋演，這樣，我們在遍歷數(shù)組的時候奸笤，用 target 減去遍歷到的數(shù)字，就是另一個需要的數(shù)字了哼鬓，直接在 HashMap 中查找其是否存在即可监右，注意要判斷查找到的數(shù)字不是第一個數(shù)字，比如 target 是4异希，遍歷到了一個 2健盒，那么另外一個 2 不能是之前那個 2绒瘦，整個實現(xiàn)步驟為：先遍歷一遍數(shù)組，建立 HashMap 映射扣癣，然后再遍歷一遍惰帽，開始查找，找到則記錄index父虑。
public class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
int[] result = new int[2];
for (int i = 0; i < nums.length; i++) {
map.put(nums[i], i);
}
for (int i = 0; i < nums.length; i++) {
int t = target - nums[i];
if (map.containsKey(t) && map.get(t) != i) {
result[0] = i;
result[1] = map.get(t);
break;
}
}
return result;
}
}
兩個算法的性能差距明顯该酗，LeetCode 的 OJ 結(jié)果如下：
