Leetcode:1.Two Sum
這是崔斯特的第八十九篇原創文章
1. Two Sum
難度: Easy
刷題內容
原題連線: https://leetcode.com/problems/two-sum
內容描述:
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: Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].
解題方案
思路 1
- 時間複雜度: O(N^2)- 空間複雜度: O(1) *
暴力解法,兩輪遍歷
beats 12.80%
class Solution(object): def twoSum(self, nums, target): """ :type nums: List[int] :type target: int :rtype: List[int] """ for i in range(len(nums)): for j in range(i+1, len(nums)): if nums[i] + nums[j] == target: return [i, j]
Runtime: 5248 ms, faster than 12.80% of Python3 online submissions forTwo Sum. Memory Usage: 13.5 MB, less than 51.76% of Python3 online submissions for Two Sum.
太嚇人,遍歷太慢了。
思路 2
A + B = target,同樣的:A = target - B,我們可以維護一個字典來記錄說訪問過的值。
這裡我犯了個錯,我先貼程式碼
class Solution: def twoSum(self, nums: List[int], target: int)-> List[int]: lookup = {} for i, j in enumerate(nums): if target - j not in lookup.values(): lookup[i] = j else: return [i, nums.index(target - i)]
Runtime: 568 ms, faster than 34.25% of Python3 online submissions forTwo Sum. Memory Usage: 14.1 MB, less than 9.73% of Python3 online submissions for Two Sum.
雖然比第一種解法好,但是才超過34.25%,這也太慢了吧。
其實是我寫法不夠好,字典維序反了,這樣查詢會慢很多,每次查詢都需要查詢 lookup.values()
,這其實是一個列表,應該就是這裡導致速度變慢。
改良後的程式碼:
class Solution: def twoSum(self, nums: List[int], target: int)-> List[int]: lookup = {} for i, j in enumerate(nums): if target - j in lookup: return [i, nums.index(target - j)] else: lookup[j] = i
Runtime: 40 ms, faster than 73.58% of Python3 online submissions for Two Sum. Memory Usage: 14.1 MB, less than 10.10% of Python3 online submissions for Two Sum.
比73.58%的要快,果然細節決定成敗啊。