Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.You can return the answer in any order.
Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
Example 2:
Input: nums = [3,2,4], target = 6
Output: [1,2]
Example 3:
Input: nums = [3,3], target = 6
Output: [0,1]
Constraints:
- 2 <= nums.length <= 104-109 <= nums[i] <= 109-109 <= target <= 109Only one valid answer exists.
Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity?
📝 題目說明
給定一個整數陣列 nums 和一個整數 target，請你從陣列中找出「兩個數」相加剛好等於 target，並回傳它們的「索引」。
⚠️ 限制：
- 每個輸入只有 一組正確答案
- 不能使用同一元素兩次
- 回傳順序不拘（例如
[1,2]或[2,1]都行）
🧠 解題思路
解法 1：暴力法（Brute Force）
雙層迴圈，把所有組合檢查一次。
時間複雜度：O(n²)
→ n 最大到 10⁴，這方法能解但效率不高。
程式碼：
def twoSum(nums, target):
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] == nums[j] == target / 2 and i != j:
return [i, j]
if nums[i] + nums[j] == target:
return [i, j]
解法 2：哈希表（Hash Map）——先存再找
思路：
建一個字典（map），將每個數字與索引記錄起來， 再檢查 target - nums[i] 是否在 map 中。
時間複雜度：O(n)
空間複雜度：O(n)
程式碼：
def twoSum(nums, target):
hash_dit = {}
for i,num in enumerate(nums):
diff = target - num
if diff in hash_dit:
return hash_dit[diff] , i # 剛好加起來是 target
hash_dit[num] = i #找不到就先存起來
print('不在此列表')
🧠 哈希表的核心概念
🔹 Key → Value 直接定位
一般列表（list）是靠「位置」找資料，例如 nums[3]。
但字典（hash table）是靠「key」找資料，例如 price["apple"]。
哈希表存取方式：
table[key] = value # 存
value = table[key] # 取
時間複雜度：
- 查詢：O(1)
- 新增：O(1)
- 刪除：O(1)
非常快。
🧪 測試
nums = [2,7,11,15,17,20,50,90]
target = 110
結果索引(5,7) 驗算nums[5] + nums[7] = 20 + 90 =110 剛好為我們target值
