經典 字典應用題 兩數之和 Two Sum_Leetcode #1
題目敘述
題目會給我們一個陣列，要求我們返回 兩數之和=target所在的陣列索引值。
題目還額外保證，一定剛好有一組解。
對應的中文教學影片
搭配服用，效果更佳~
測試範例
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 <= 10^4-10^9 <= nums[i] <= 10^9-10^9 <= target <= 10^9- Only one valid answer exists.
演算法
除了第一直覺的暴力雙層迴圈搜索之外，其實還有一個更高效率的字典演算法。
題目已經給定two sum的定義如下
x + y = nums[i] + nums[j] = target, where i =/= j
移項得到
y = nums[j] = target - nums[i]
= nums[i] 遇到誰，相加就可以等於target
= x 遇到誰，相加就可以等於target
= 互補的值，相加就可以等於target
因此，我們可以建立一個字典，key就是當下的陣列元素，value則對應到當下的陣列索引值array index。
從左到右，依序掃描每一個陣列元素，假如在字典中找到nums[i]所需要的互補的值，兩者相加等於target，那麼回傳當下這組two sum的陣列索引值，就是答案！
題目一開始有保證，一定存在恰好一組解。
程式碼
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
# key: number
# value: index
history = {}
for index, x in enumerate(nums):
y = target - x
# look-up table
if y in history:
# there exists a pair, x + y = target
return [ history[y], index]
# update table, save x's index into history
history[x] = index
return [-1, -1]
複雜度分析
時間複雜度: O(n)
線性掃描，從左到右掃描每個陣列元素，總共耗時O(n)
空間複雜度: O(n)
建立了一個字典，大小最大為元素總數，所占空間為O(n)
關鍵知識點
題目一開始有保證，一定存在恰好一組解。
我們可以建立一個字典，key就是當下的陣列元素，value則對應到當下的陣列索引值array index。
從左到右，依序掃描每一個陣列元素，假如在字典中找到nums[i]所需要的互補的值，兩者相加等於target，那麼回傳當下這組two sum的陣列索引值，就是答案！
Reference:
[1] Python/JS/Go/C++ O(n) by dict. [w/ Hint] - Two Sum - LeetCode
