經典 字典應用題 兩數之和 Two Sum_Leetcode #1

Clay Banks on Unsplash

題目敘述

題目會給我們一個陣列，要求我們返回 兩數之和=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