LeetCode #1 #167 #653 Two Sum

最近再嘗試使用 Go 來解 LeetCode 上的題目，剛好解完這三個非常相似的簡單題目，因此寫下筆記紀錄。

這三個題目 #1 #167 #653 都是一個很基本的演算法問題，給一組數字的輸入以及目標數字，求那組數字中是否有任意兩個數字相加後，會相等於目標數字？

這個三題目的原則上輸入的資料結構與條件都不太一樣，輸出也不太相同：

#	輸入	輸出
#1	數字陣列 []int	兩個數字的索引位置
#167	數字陣列 []int，但是數字升冪排序	兩個數字的索引位置+1
#653	自定義的 Tree 結構	是否存在該兩個數字的組合

LeetCode #1 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.

LeetCode #167 Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number. The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based. You may assume that each input would have exactly one solution and you may not use the same element twice.

LeetCode #653 Given a Binary Search Tree and a target number, return true if there exist two elements in the BST such that their sum is equal to the given target.

題目解題

#1 看懂題目後，從數列中找到兩個位置的數字，其數字相加會等於目標數字，可以很直覺寫出使用兩個迴圈，複雜度為 O(n^2) 的演算法 (Algorithmic complexity)：

func twoSum(nums []int, target int) []int {
   for ii := 0; ii < len(nums); ii++ {
      for kk := ii + 1; kk < len(nums); kk++ {
         if nums[ii]+nums[kk] == target {
            return []int{ii, kk}
         }
      }
   }
   panic("bad input")
}

#167 與 #1 相同的邏輯，但因為有排序過，所以可以採取與 #1 不同的演算法，原則上第一個數字決定後，應該使用 Binary search 來尋找第二個數字，使得演算法複雜度為 O(n*log(n))：

func twoSum(nums []int, target int) []int {
   for ii := 0; ii < len(nums); ii++ {
      want := target - nums[ii]

      start := ii + 1
      end := len(nums) - 1
      for start <= end {
         target := start + (end-start+1)/2
         if nums[target] == want {
            return []int{ii+1, target+1}
         } else if nums[target] < want {
            start = target + 1
         } else {
            end = target - 1
         }
      }
   }
   panic("bad input")
}

#653 跟 #1 相似，只是輸入不再是數字陣列而是 BST (Binary Search Tree)，直覺想到得簡單的做法是，把 BST 裏頭的數字倒出來倒成為數字陣列，然後套用 #1 的演算法直接解決，至於要用哪種順序 Inorder (Left, Root, Right)、Preorder (Root, Left, Right) 或者是 Postorder (Left, Right, Root) 似乎就沒有什麼差別了：

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func findTarget(root *TreeNode, target int) bool {
   nums := make([]int, 0, 100)
   var f func(node *TreeNode)
   f = func(node *TreeNode){
      nums = append(nums, node.Val)
      if node.Left != nil{
         f(node.Left)
      }
      if node.Right != nil{
         f(node.Right)
      }
   }
   if (root == nil){
      return false
   }

   f(root)
   for ii := 0; ii < len(nums); ii++ {
      for kk := ii + 1; kk < len(nums); kk++ {
         if nums[ii]+nums[kk] == target {
            return true
         }
      }
   }

   return false
}

演算法封裝

這三個題目可以用 #1 的暴力演算法解 (brute force)，若考慮有不同的輸入資料結構，再考慮不像原先 #653 需額外建立空間情況下，嘗試使用設計模式包裝解法來處理，因此先建立資料取得的抽象化界面，使用經典的 Iterator 迭代子，需要回傳 Key & Value，為什麼是如此設計 Iterator 可以參考這篇：Golang Iterator Channel Implementation。此外為了適用於 #653 的資料結構，Key 並不指定型別 (Go1.x 沒有支援 Generic…)：

import (
   "context"
)

type Pair struct {
   Key interface{}
   Value int
}

type Iterator interface {
   Iterator(ctx context.Context) <-chan Pair
}

之後封裝 #1 解題的演算法，很明顯的以下實務效能會比原先的解法差，但因為封裝輸入資料，會少了許多可用的假設，所以只能先這樣接受它：

func twoSumEx(nums Iterator, target int) []interface{} {
   ctx1, cancel := context.WithCancel(context.Background())
   defer cancel()
   for r1 := range nums.Iterator(ctx1) {
      ctx2, cancel := context.WithCancel(context.Background())
      defer cancel()
      for r2 := range nums.Iterator(ctx2) {
         if r1.Key != r2.Key && r1.Value+r2.Value == target {
            return []interface{}{r1.Key, r2.Key}
         }
      }
   }
   return nil
}

針對 #1, #167 的輸入資料結構 []int，實作其 Iterator 介面：

type intIterator []int

func (i intIterator) Iterator(ctx context.Context) <-chan Pair {
   c := make(chan Pair)
   go func() {
      defer close(c)
      for key, value := range i {
         select {
         case c <- Pair{key, value}:
            break
         case <-ctx.Done():
            return
         }
      }
   }()
   return c
}

針對 #653 的輸入資料結構 TreeNode，實作其 Iterator 介面：

type treeNodeIterator TreeNode

func (t treeNodeIterator) Iterator(ctx context.Context) <-chan Pair {
   c := make(chan Pair)

   var f func(node *TreeNode) bool
   f = func(node *TreeNode) bool {
      select {
      case c <- Pair{node, node.Val}:
         break
      case <-ctx.Done():
         return false
      }

      ok := true
      if node.Left != nil && ok {
         ok = f(node.Left)
      }
      if node.Right != nil && ok {
         ok = f(node.Right)
      }
      return ok
   }

   go func() {
      defer close(c)
      f((*TreeNode)(&t))
   }()
   return c
}

最後關於解答套用以上的宣告，通通可以使用相同的函數處理：

// #1
func twoSum(nums []int, target int) []int {
   r := twoSumEx(intIterator(nums), target)
   if r == nil {
      panic("bad input")
   }
   return []int{r[0].(int), r[1].(int)}
}

// #167
func twoSum(nums []int, target int) []int {
   r := twoSumEx(intIterator(nums), target)
   if r == nil {
      panic("bad input")
   }
   return []int{r[0].(int) + 1, r[1].(int) + 1}
}

// #653
func findTarget(root *TreeNode, k int) bool {
   r := twoSumEx((*treeNodeIterator)(root), k)
   return r != nil
}

演算法再優化，使用 map

已知 twoSumEx 演算法複雜度是 O(n^2)，可以在進行演算法優化，若假設 map 查詢是 O(1)，可以利用一個 map 來儲存之前所記錄的結果，使得演算法複雜度變成 O(n)，用空間換時間：

func twoSumEx(nums Iterator, target int) []interface{} {
   ctx, cancel := context.WithCancel(context.Background())
   defer cancel()
   cache := make(map[int]interface{})
   for r := range nums.Iterator(ctx) {
      want := target - r.Value
      if key, ok := cache[want]; ok {
         return []interface{}{key, r.Key}
      }
      cache[r.Value] = r.Key
   }
   return nil
}

由於三個問題解法都使用這封裝的 twoSumEx，以上的演算法優化不用修改原本程式，可是直接替換，這是封裝演算法的好處，但這對於這種簡單的程式問題，這是過度設計 (overdesign) 啊……。