128.Two Sum

題目：

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].

解答：

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

詳解:

暴力破解時間復雜度為O（n²），舍棄不用

HashMap是常數級的查找效率，只遍歷一個數字，另一個數字使用HashMap建立數字和其坐標位置之間的映射，所以時間復雜度為O（n）。