LeetCode 解題練習：Two Sum (Easy)
If you like this post, please click the ads on the blog or buy me a coffee. Thank you very much.
題目原文描述 https://leetcode.com/problems/two-sum/description/
中文描述
指定一個整數陣列 nums 以及一個整數 target，找出在陣列中的兩個整數總合為 target 之索引位置。可以假設每組測試資料剛好只有一組不重複的答案，且一個陣列元素只會使用一次。
範例一：
輸入 nums = [1, 3, 5, 9], target = 8
輸出 [1, 2]
因為 nums[1] + nums[2] = 3 + 5 = 8
範例二：
輸入 nums = [1, 3, 5, 2, 9], target = 10
輸出 [0, 4]
因為 nums[0] + nums[4] = 1 + 9 = 10
解法一：暴力法 Brute Force
使用迴圈找出陣列中任兩個元素 nums[i] + nums[j] 的總和是否等於 target 。
Python Code
if nums[i] + nums[j] == target:
解法二：兩階段查表法 ( two-pass hash table)
第一階段將陣列元素的值當成查詢的鍵值 key，陣列元素的索引當成查詢的值 value。以 nums = [1, 3, 5, 9] 為例，將會建立一個如下的 hash table：
然後檢查 target — nums[i] 是否存在此 hask table 的鍵值中。
Python Code
return [i, hashTable[diff]]
解法三：一階段查表法 ( one-pass hash table)
在建立 hash table 時，可以先檢查 target — nums[i] 是否存在此 hash table 的鍵值中，再建立 hash table。
Python Code
return [i, hashTable[diff]]
hashTable[nums[i]] = i # 先檢查再建立 hash table
Originally published at https://yunlinsong.blogspot.com.