1. 題目描述

LeetCode 1. 兩數之和（Two Sum）

給定一個整數數組 nums 和一個目標值 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）

我們可以使用 哈希表（HashMap）來存儲數組中已經遍歷過的元素及其索引。

思路如下：

1. 遍歷 nums 數組，對于每個元素 nums[i]，計算它的補數 target - nums[i]。

2. 檢查這個補數是否已經存在于 HashMap 中。

   • 如果存在，說明找到了滿足條件的兩個數，返回它們的索引。

   • 如果不存在，將 nums[i] 及其索引存入 HashMap，繼續遍歷。

---

3. Java 代碼實現

class Solution {public int[] twoSum(int[] nums, int target) {Map<Integer, Integer> ma = new HashMap<>();int[] ans = new int[2];for (int i = 0; i < nums.length; i++) {int tmp = target - nums[i];if (ma.containsKey(tmp)) {ans[0] = ma.get(tmp);ans[1] = i;return ans; // 立即返回，避免繼續遍歷} else {ma.put(nums[i], i);}}return ans; // 題目保證一定有解}
}

4. 復雜度分析

• 時間復雜度：O(n)

  • 只需遍歷數組一次，每次操作（查找和插入 HashMap）都是 O(1) 的時間復雜度。

• 空間復雜度：O(n)

  • 需要存儲 nums 中最多 n 個不同的元素。

---

5. 總結

1. 該題目是經典的哈希表應用，利用 HashMap 可以高效查找所需的數值。

2. 通過 target - nums[i] 計算補數，并在 HashMap 中查找是否存在，可以快速確定答案。

3. 代碼整體邏輯清晰，時間復雜度 O(n)，適用于大多數情況。

希望這篇文章能幫助你理解 兩數之和（Two Sum） 的解法！