題目：給定一個整數(shù)數(shù)組 nums 和一個整數(shù)目標(biāo)值 target，請你在該數(shù)組中找出 和為目標(biāo)值 target 的那 兩個 整數(shù)，并返回它們的數(shù)組下標(biāo)。
你可以假設(shè)每種輸入只會對應(yīng)一個答案。但是，數(shù)組中同一個元素在答案里不能重復(fù)出現(xiàn)。
你可以按任意順序返回答案。

示例 1：
輸入：nums = [2,7,11,15], target = 9
輸出：[0,1]
解釋：因為 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

方法一：暴力求解

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int n = nums.length;
        for (int i = 0; i < nums.length-1; ++i) {
            for (int j = i + 1; j < nums.length; ++j) {
                //如果j用1開始的話，容易和i重復(fù)
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[0];
    }
}

方法二：哈希表
在遍歷的同時，記錄一些信息，以省去一些循環(huán)，以空間換時間的想法。需要記錄已遍歷的數(shù)值和它所對應(yīng)的下標(biāo)。

圖片.png

target是8，6在之前沒有元素2與之對應(yīng)，所以放入hash表中，value為0，3在之前沒有元素5與之對應(yīng)，所以放入hash表中，value為1，8在之前沒有元素0與之對應(yīng)，所以放入hash表中，value為2，2在于之前的6所對應(yīng)，所以輸出[0,3]。

    public int[] twoSum(int[] nums, int target) {
        //初始化哈希表的時候盡量指定哈希表的容量，以避免哈希表擴(kuò)容所帶來的性能消耗
        Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>(nums.length -1);
        //由于在第一個元素之前一定沒有其他元素與之對應(yīng)，因此直接放入hash表中
        hashMap.put(num[0],0);
        //從下標(biāo)為1的第一個元素開始遍歷
        for (int i = 1; i < nums.length; ++i) {
            //每次之前都需要檢查在它之前是否有對應(yīng)的元素在不在哈希表中
            if (hashtable.containsKey(target - nums[i])) {
                return new int[]{hashtable.get(target - nums[i]), i};
            }
            hashMap.put(num[i],i);
        }
        return new int[0];
    }
}

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