Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

 1234 Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1]. 

Related Topics: Hash TableArray

## 解題邏輯與實作

### 暴力法

 1234567891011121314151617 class Solution: def cal_sum(self, num_1 , num_2): return num_1 + num_2 def twoSum(self, nums, target): size = len(nums) for idx1 in range (size) : num_1 = nums[idx1] for idx2 in range(idx1+1 ,size): num_2 = nums[idx2] s = self.cal_sum(num_1,num_2) if s == target: return [idx1,idx2] raise RuntimeError("No two sum solution") 

### 雜湊表（Hash table)

1. 讀入陣列中一值 n，並計算其差值 diff = target - i
2. 檢查差值 diff ，是否存在於 HashMap 中，
1. 不存在，將 n 與所對應的索引值作為 key–value pair，存入 HashMap 中。
• 因為，題目要求最後回傳的結果是兩個數字的索引值，所以必須一併記錄索引值。
2. 存在，則取出差值 diff 所對應的索引值，與當前索引值合併成一個陣列回傳。
 123456789 class Solution: def twoSum(self, nums, target): keys = {} for idx, value in enumerate(nums): diff = target - value if diff in keys: return [keys[diff], idx] keys[value] = idx