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.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
難度：easy
解析：在給定數(shù)組之中，得到兩個數(shù)字确沸，這兩個數(shù)字之和等于給定數(shù)字惠啄，返回兩數(shù)字的序號下標。由于題干中已經(jīng)表明有且只有一組解棋傍，因此不用考慮很多異常情況，只需得到該答案即可纺阔。
方法一：窮舉遍歷（★★★）
最簡單的方法就是窮舉遍歷转绷，計算所有數(shù)字兩兩之和，直至得到答案戈毒。
class Solution {
public int[] twoSum(int[] nums, int target) {
for ( int i = 0 ; i < nums.length ; i++){
for ( int j = i + 1 ; j < nums.length ; j++){
if(nums[i] + nums[j] == target){
return new int[] {i,j};
}
}
}
return null;
}
}
結果：Runtime: 26 ms艰猬，beats 33.69% of Java submission.
備注：遍歷數(shù)組，時間復雜度O(n^2)埋市，顯然這個操作很一般冠桃。
方法二：Map篩選（★★★★）
添加map作為篩選條件。遍歷給出的數(shù)組道宅，對于任意數(shù)字nums[i]食听，如果map中不包含nums[i]，則將鍵值對（target-nums[i]污茵，i）置于map中碳蛋，如果map中包含nums[i]，則｛i省咨，map.get(nums[i])｝為所求答案。
因為有且僅有一組解玷室，假設a1零蓉，a2為這組解，則a1會先置于map中穷缤，且鍵值對為（target-nums[a1]敌蜂，a1），當遍歷到nums[a2]時津肛，可知map包含nums[a2]（即 nums[a2] == target-nums[a1]）章喉，故可得答案為數(shù)組｛a1，a2｝。
class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer,Integer> map = new HashMap();
for( int i = 0 ; i < nums.length ; i++){
if(map.containsKey(nums[i])){
return new int[] { map.get(nums[i]) ,i};
}else{
map.put((target - nums[i]),i);
}
}
return null;
}
}
結果：Runtime: 4 ms秸脱，beats 90.71% of Java submission.
備注：遍歷數(shù)組落包，時間復雜度O(n)，同時使用HashMap進行key-value尋值摊唇，尋找這個唯一解咐蝇。
方法三：數(shù)組篩選（★★★★★）----所有用戶提交通過的答案中的最佳方法之一
此方法和方法二的思路基本一致，只不過方法二是使用map進行尋值巷查，此方法是使用數(shù)組進行尋值有序。其主要思路如下，新建一個數(shù)組arr岛请，保存未尋得配對的數(shù)字旭寿，保存方式：arr[ nums[ i ] ] = i。
遍歷原數(shù)組nums崇败，對于原數(shù)組任一數(shù)字nums[ i ]盅称，前往arr中尋值，如果arr[ target - nums[ i ] ] > 0僚匆，則代表目標值尋得微渠，答案為{ i ，arr[ target - nums[ i ] ] }咧擂，如果arr[ target - nums[ i ] ] == 0逞盆，為默認值，則代表目標值未插入arr松申，將當前值插入arr中云芦。
備注：此方法有幾個注意點，
（1）diff&max贸桶，nums[i]&max舅逸，這兩處且運算是為了防止diff和nums[i]大于2048導致超界無法插入arr中；
（2）“ 如果arr[ target - nums[ i ] ] == 0皇筛，為默認值琉历，則代表目標值未插入arr ”，這一結論并非絕對正確的水醋，可能0就是目標值的位置旗笔，而不是默認值0，所以需要在一開始對nums[0]進行判斷之后拄踪，arr[ target - nums[ i ] ] == 0才可以認為是默認值0.
class Solution {
public int[] twoSum(int[] nums, int target) {
int[] arr=new int[2048];
int max=arr.length-1;
int first=nums[0];
for(int i=1;i<nums.length;i++){
int diff=target-nums[i];
if(first==diff){
return new int[]{0,i};
}
int index=arr[diff&max];
if(index!=0){
return new int[]{index,i};
}
arr[nums[i]&max]=i;
}
return null;
}
}
結果：Runtime: 1 ms蝇恶，beats 99% of Java submission.
備注：遍歷數(shù)組，時間復雜度O(n)惶桐，同時使用數(shù)組進行尋值撮弧，尋找這個唯一解潘懊。
