T1. Two Sum 【Easy】

題目

給定一個(gè)數(shù)組和一個(gè)目標(biāo)數(shù)，從數(shù)組中找到兩個(gè)數(shù)，使得這兩個(gè)數(shù)之和等于這個(gè)目標(biāo)數(shù)，返回兩個(gè)數(shù)組的編號(hào)。

Example

給定一個(gè)數(shù)組 nums = [2, 7, 11, 15], target = 9,
因?yàn)?nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

代碼一

看到題目第一反應(yīng)就想到如下的答案，問(wèn)小學(xué)生這個(gè)問(wèn)題他應(yīng)該也是這個(gè)思路哈哈~不過(guò)復(fù)雜度就是O（n2）了。

/**
 * 初始化一個(gè)數(shù)組a，通過(guò)兩個(gè)循環(huán)，一個(gè)個(gè)加過(guò)去得到正確的
 * 答案則返回
 */
public class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] a=new int[2];
        for(int i=0;i<nums.length;i++){
            int x=nums[i];
            for(int j=i+1;j<nums.length;j++){
                if(x+nums[j]==target){
                    a[0]=i;
                    a[1]=j;
                    return a;
                }
            }
            
        }
        return a;
    }
}

代碼二

這是 Top Solution 的解決方法,復(fù)雜度變?yōu)榱薕（n）（這是提供答案的人說(shuō)的，感覺(jué)也能說(shuō)是O（nlogm）

/**
 * 和前面的差別在于用了一個(gè)HashMap,這個(gè)思路是不斷把數(shù)值讀入，利用map.containsKey
 * 方法來(lái)搜索。
 */
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++) {
        //這里用了target - numbers[i]，如果map里有，就直接找到了兩個(gè)答案
        if (map.containsKey(target - numbers[i])) {
            result[1] = i + 1;
            //通過(guò)Map的get方法得到標(biāo)號(hào),這里得到的是兩個(gè)數(shù)中遍前面的數(shù)，因此給result[0]
            result[0] = map.get(target - numbers[i]);
            //返回正確結(jié)果
            return result;
        }
        map.put(numbers[i], i + 1);
    }
    return result;
}

思路

寫在代碼注釋里面

補(bǔ)充

關(guān)于 Map 以及它的常用方法

map儲(chǔ)存的是鍵（KEY）值(VALUE)對(duì)，簡(jiǎn)單介紹一下它在代碼中出現(xiàn)的方法

put(object key,object value);//存入

get(object key);//根據(jù)key值找出對(duì)應(yīng)的value值

containsKey(object key);(判斷鍵是否存在)

containsValue(object value);(判斷值是否存在)