題目出處
https://leetcode.com/problems/two-sum/
難度
Easy
個人範例程式碼 – 三刷 (2022/04/06)
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
list_number_and_index = [(ele, idx) for idx, ele in enumerate(nums)]
list_number_and_index.sort()
start, end = 0, len(nums)-1
while(start < end):
if list_number_and_index[start][0] + list_number_and_index[end][0] == target:
return sorted([list_number_and_index[start][1], list_number_and_index[end][1]])
elif list_number_and_index[start][0] + list_number_and_index[end][0] < target: # need bigger
start += 1
else: # nums[start] + nums[end] > target: # need smaller
end -= 1
else:
return [-1, -1]
算法說明 – two pointers
這次使用 two pointers 的作法,這個做法的優點是可以比較下表,
基本上就是能節省掉 hashmap 的空間,取而代之的是比較多的時間
空間可以換時間,時間可以換空間。 這個觀念非常的重要!!!
hashmap | two pointers | |
---|---|---|
空間複雜度 | O(n) | O(1) |
時間複雜度 | O(1) | O(n), 但有前置步驟 sort = O(nlogN) |
最近在練習程式碼本身就可以自解釋的 Coding style,可以嘗試直接閱讀程式碼理解
input handling
處理沒有結果的狀況 [-1, -1]
Boundary conditions
two pointers 循環條件 while(start < end)
補充:list comprehesion
list_number_and_index = [(ele, idx) for idx, ele in enumerate(numbers)]
補充:dict comprehesion
dict_number_to_index = {ele: idx for idx, ele in enumerate(numbers)}
個人範例程式碼 – 二刷 (2022/02/24)
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
mydict = {}
for idx in range(len(nums)):
# print(mydict.keys())
if nums[idx] in mydict.keys():
return [mydict[nums[idx]], idx]
else:
mydict[target - nums[idx]] = idx
個人範例程式碼 – 一刷 (2021/03/16)
class Solution:
def twoSum(self, nums, target): # 2 7 11 15
my_dict = {}
for idx, ele in enumerate(nums):
rest = target - ele
if rest in my_dict:
return [my_dict[rest], idx]
else:
my_dict[ele] = idx # record
解法 – HashTable
這題主要考的是 HashTable,
需要先建立一張表 (此處建立 dict),
利用 「key -> value」 的特性保存 「剩餘值 對應 index」
因此當後續的計算,發現剩餘值存在 dict 的 key 中,
就能快速反查表得到 index。
示意圖
(將找不到 remain value 的值,作為 key 存進 dict 中)
Reference
- 两数之和 · Two Sum
- dict comprehesion