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.
給定一個(gè)整數(shù)數(shù)組，返回兩個(gè)數(shù)的下標(biāo)，使這兩個(gè)數(shù)的和等于指定的目標(biāo)數(shù)，假定每個(gè)輸入的數(shù)組都有恰好一個(gè)解

Example:

Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

My Solution

(Java) Version 1 Time: 98ms:

　　在數(shù)組中從前往后搜索，每一個(gè)數(shù)都和其余的數(shù)進(jìn)行求和判斷，如果有結(jié)果則直接輸出，題目中已經(jīng)假設(shè)只有一個(gè)解，不需要再向后搜索

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++)
            for (int j = 0; j < nums.length; j++) {
                if (i == j)
                    continue;
                if (nums[i] + nums[j] == target)
                    return new int[] { i, j };
            }
        return nums;
    }
}

(Java) Version 2 Time: 52ms:

　　對(duì)上一個(gè)算法的改進(jìn)在于，第一次循環(huán)搜索的數(shù)之前的數(shù)不需要再在第二個(gè)循環(huán)重新判斷一次，每一次循環(huán)都只需要和后面的數(shù)作比較，前面的數(shù)在上一次循環(huán)中已經(jīng)被比較過一次了，同時(shí)，因?yàn)椴恍枰懊娴臄?shù)進(jìn)行比較，那么，比較可以跳過自己，直接從i+1開始，省去了判斷i==j的步驟

public 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 nums;
    }
}

(Java) Version 3 Time: 8ms (By plover ):

　　運(yùn)用Java的Map，構(gòu)造Map鍵為當(dāng)前判斷的數(shù)的期望目標(biāo)數(shù)，值為數(shù)的下標(biāo)，通過搜索鍵來(lái)判斷是否存在對(duì)應(yīng)的期望目標(biāo)數(shù)，并可以快速找到其下標(biāo)，不需要重新循環(huán)一次。巧妙應(yīng)用Map把數(shù)組中的數(shù)和下標(biāo)綁定在一起，達(dá)到快速獲得數(shù)及其下標(biāo)的目的

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> pair=new HashMap<>();
        int result[] = new int[2];
        for(int i=0;i<nums.length;i++){
            if(pair.containsKey(nums[i])){
                result[0]=pair.get(nums[i]);
                result[1]=i;
                return result;
            }
            else{
                pair.put(target-nums[i], i);
            }
        }
    return result;
    }
}