167. Two Sum II – Input array is sorted

# Approach 1. Two Pointers
# Time Complexity: O(n)
# Space Complexity: O(1)
class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        i = 0
        j = len(numbers) - 1
        # because we assume it has exactly one solution, we don't need to consider i > j case
        while numbers[i] + numbers[j] != target:
            if numbers[i] + numbers[j] > target:
                # the sum is too large, move j
                j -= 1
            else:
                # the sum is too small, move i
                i += 1
        # because the indices are 1-indexed, return i+1 and j+1
        return [i + 1, j + 1]

Notes:

程式流程

• 根據題目說明，一定有唯一解存在，所以忽略一些corner cases的判斷
• Pseudo-code

  i = representing the first element (0)
  j = representing the last element (length - 1)
  
  while numbers[i] +  numbers[j] != target
      if numbers[i] + numbers[j] is greater than target, we shift the right pointer to left ( j = j -1)
      if numbers[i] + numbers[j] is smaller than target, we shift the left pointer to right ( i = i + 1)
  
  found pair and return [i+1, j+1]

紀錄

• 5分鐘 ： 寫下題目大綱、需要的假設、method的input與output
• 5分鐘 ： 考慮binary search solution，但是time complexity是O(nlogn)，比起non-sorted array版本 (hash)還慢，所以並未實作
• 10分鐘寫下pseudo code，並轉成Python code，舉幾個例子用手寫(模擬)的方式跑過一次程式碼
• 5分鐘：把手寫的程式碼輸入Leetcode並執行

備註

• 題目給的假設簡化了程式的判斷，例如不需要考慮找不到解答的情況，但是如果面試的時候並沒有這些假設，coding的時候要特別注意一些 corner cases
• 比起原本的two sum版本，不需要額外的空間 (Space Complexity: O(1))