題目出處
167. Two Sum II – Input Array Is Sorted
難度
medium
個人範例程式碼 – two pointers
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
if not numbers:
return [-1, -1]
start, end = 0, len(numbers)-1
while(start < end):
if(numbers[start] + numbers[end] == target):
return [start+1, end+1]
elif(numbers[start] + numbers[end] < target): # smaller
start+= 1
else: # (numbers[start] + numbers[end] > target):
end -= 1
else:
return [-1, -1]
算法說明
這題我們在之前的題目已經有詳細說明了,可參考:
另外,這題因為有「已經排序」的特性,目的就是為了解決表格中的 sort,
加速 two pointers 做法的時間複雜度。
hashmap | two pointers | |
---|---|---|
空間複雜度 | O(n) | O(1) |
時間複雜度 | O(1) | O(n), 但有前置步驟 sort = O(nlogN) |
最近在練習程式碼本身就可以自解釋的 Coding style,可以嘗試直接閱讀程式碼理解
input handling
處理沒有 input 的狀況,return [-1, -1]
Boundary conditions
start < end,交錯或等於就結束
Reference
⭐ Leetcode 解題紀錄 ⭐ | 題型 | 資料結構 | Python Solution | C++ Solution | Note | |
---|---|---|---|---|---|---|
⭐BFS 相關題型 ⭐ | ||||||
104 | Maximum Depth of Binary Tree | BFS (分層) | Python | |||
94 | Binary Tree Inorder Traversal | BFS (分層) | Tree | Python | 內含 處理 Tree 樹問題的重點 | |
102 | Binary Tree Level Order Traversal | BFS (分層) | Tree | Python | ||
103 | Binary Tree Zigzag Level Order Traversal | BFS (分層) | Tree | Python | ||
107 | Binary Tree Level Order Traversal II | BFS (分層) | Tree | Python | ||
133 | Clone Graph | BFS (分層) | Graph | Python | Graph 的基本操作 #重要題型 | |
127 | Word Ladder | BFS (分層), DFS | Graph | Python | ||
[Lint] 127 | Topological Sorting | BFS (拓撲) | Python | 內有 indegree, outdegree 介紹 #重要題型 | ||
207 | Course Schedule | BFS (拓樸) | Graph | Python | ||
210 | Course Schedule II | BFS (拓樸) | Graph | Python | ||
[Lint] 892 | Alien Dictionary | BFS (拓樸) | Graph | Python | ||
[Lint] 431 | Connected Component in Undirected Graph | BFS (連通塊) | Graph | Python | 內含 BFS 模板 #重要題型 | |
1091 | Shortest Path in Binary Matrix | BFS (最短路徑) | Matrix | Python | ||
⭐ Binary Serach 相關題型 ⭐ | ||||||
33 | Search in Rotated Sorted Array | Binary Serach | Array | Python | # |