LeetCode_數組_簡單_1.兩數之和

目錄

• 1.題目
• 2.思路
• 3.代碼實作（Java）

1.題目

給定一個整數數組 nums和一個整數目标值 target，請你在該數組中找出和為目标值 target的那兩個整數，并傳回它們的數組下标。

你可以假設每種輸入隻會對應一個答案。但是，數組中同一個元素在答案裡不能重複出現。

你可以按任意順序傳回答案。

示例 1：

輸入：nums = [2,7,11,15], target = 9

輸出：[0,1]

解釋：因為 nums[0] + nums[1] == 9，傳回 [0,1] 。

示例 2：

輸入：nums = [3,2,4]，target = 6

輸出：[1,2]

示例 3：

輸入：nums = [3,3]，target = 6

輸出：[0,1]

提示：

2 <= nums.length <= 104

-109 <= nums[i] <= 109

-109 <= target <= 109

隻會存在一個有效答案

來源：力扣（LeetCode）

連結：https://leetcode-cn.com/problems/two-sum

2.思路

（1）暴力窮舉法

暴力窮舉法應該是最容易想到的方法，其思想是使用兩層for循環，周遊數組中的每一個數x，查找數組中是否存在target-x，若存在，将結果儲存到數組res中，并退出循環。

（2）哈希表法

先建立一個哈希表，對于數組真的每一個x，首先查詢哈希表中是否存在target-x，如果不存在，則将x插入到哈希表中并繼續通路下一個x，否則将答案儲存到數組res中。不過該算法的一個缺點是需要用到一個hash表，這樣一來增加了空間複雜度。

3.代碼實作（Java）

//（1）暴力窮舉法
public int[] twoSum(int[] nums, int target) {
    int[] res=new int[2];
    boolean flag=false;
    for(int i=0;i<nums.length;i++){
        for(int j=i+1;j<nums.length;j++){
            if(nums[i]+nums[j]==target){
                res[0]=i;
                res[1]=j;                
                flag=true;
            }
        }
        //由于每種輸入隻會對應一個答案，是以當找到一種答案時，可以終止查找
        if(flag){
            break;
        }
    }
    return res;
}
           

//（2）哈希表法
public int[] twoSum(int[] nums, int target) {
    Map<Integer,Integer> ht = new HashMap<Integer, Integer>();
    for (int i=0;i<nums.length;i++) {
    	//containsKey():檢查hashMap中是否存在指定的key對應的映射關系。
        if (ht.containsKey(target-nums[i])){
        	//get():擷取指定key對應對value
            return new int[]{ht.get(target-nums[i]), i};
        }
        //目前未找到target-nums[i]，将nums[i]以及其數組下标儲存到哈希表ht中，以便于下次尋找
        ht.put(nums[i], i);
    }
    return new int[0];
}