LeetCode 第1題:Two Sum
題目
給出一個整數陣列,找出其中的兩個整數,使相加等於指定整數,並返回這兩個整數的索引。
假設每組輸入只有一種解法,並且不能重複使用同一個元素。
舉例:
給出 nums = [2, 7, 11, 15], target = 9, 因為 nums[0] + nums[1] = 2 + 7 = 9, 所以返回 [0, 1].
思路
題目中提到只會有一種解法,那就意味著不會有重複的整數,不然就會有多解。
既然沒有重複的,那用一個雜湊來儲存資料就最合適了,整數為鍵,索引為值。
那我們要找兩個整數的索引就很方便了,在遍歷陣列的時候,檢查和目標的差值是否在雜湊中,有的話就是答案了。
Go 實現
func twoSum(nums []int, target int) []int { h := make(map[int]int) for i, value := range nums { if wanted, ok := h[value]; ok { return []int{wanted, i} } else { h[target-value] = i } } return nil }
執行時間:4ms,超過100%的 golang 提交。
Python3 重寫
class Solution: def twoSum(self, nums, target): """ :type nums: List[int] :type target: int :rtype: List[int] """ h = {} for i, value in enumerate(nums): if value in h: return [h[value], i] else: h[target - value] = i return None
執行時間:52ms,超過47.04%的 python3 提交。
Python3 優化
從上面的資料上看效率有點低,應該是enumerate
生成迭代器效率稍差,所以換用range(len(...))
的寫法。
class Solution: def twoSum(self, nums, target): """ :type nums: List[int] :type target: int :rtype: List[int] """ h = {} for i in range(len(nums)): value = nums[i] if value in h: return [h[value], i] else: h[target - value] = i return None
執行時間:36ms,超過99.71%的 python3 提交。