java實作兩數之和

• 1、題目原題
• 2、思路及算法
• 3、代碼實作：

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、思路及算法

我們需要能夠快速尋找數組中是否存在目标元素。如果存在，我們需要找出它的索引。

使用哈希表hashMap，可以将尋找 target - x 的時間複雜度降低到從 O(N) 降低到 O(1)。

這樣我們建立一個哈希表，對于每一個 x，我們首先查詢哈希表中是否存在 target - x，然後将 x 插入到哈希表中，即可保證不會讓 x 和自己比對

3、代碼實作：

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        # map對應key為數組值，value為數組下标序号值
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(target - nums[i])) {
                return new int[] {map.get(target - nums[i]), i};
            }
            map.put(nums[i], i);
        }
        return new int[]{0};
    }
}