710 - Python LeetCode

【Leetcode】python - [167] Two Sum II - Input Array Is Sorted 個人解法筆記

題目出處

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 做法的時間複雜度。

hashmaptwo 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