使用typescript類型實現ThreeSum

Posted on by

前言

本文執行環境typescript，版本4.7.4

不使用typescript的計算能力，通過類型來實現ThreeSum

思路整理

實現ThreeSum之前我們先降低下難度，實現TwoSum，因為TwoSum可以作為ThreeSum的基礎泛型

TwoSum需要準備什麼呢？

  • 遞歸元組，模擬for循環
  • 減法，遞歸過程中求出差值
  • 對每一項差值判斷是否存在

完成TwoSum後如何實現ThreeSum？

  • 每一項和剩餘元組走一遍 TwoSum泛型，篩選滿足條件的
  • 為瞭保證每一項能夠走TwoSum泛型，對於元組大到小排序

實現TwoSum

實現減法

因為元組下標是遞增有序數列，我們在每次遞歸的時候返回一個長度+1的新元組並獲取長度，就可以對非負整數依次點名瞭

如求A – B，我們假設A – B永遠是非負整數數，無限遞歸產生新元祖的過程中，排查掉A和B相等後，必定是先點名到B，然後點名到A，而B 到 A的遞歸次數就是差值，也就是求得的結果

實現這個差值的計算

  • A作為被減數，R作為長度與減數相等的數組，Z則用於遞歸累增
  • 當被減數R長度等於A的過程中，Z則是被減數和減數的差值
type GetLen<A extends number, R extends number[], Z extends number[] = []> =
  A extends R['length'] ? Z['length'] : GetLen<A, [...R, 0], [...Z, 0]>;

減法如下：

  • 排除掉A和B相等的情況
  • 前提條件：A大於或者等於B
  • 用差值泛型求A 和 B的差
type Subtract<A extends number, B extends number, R extends number[] = []> =
  A extends B ? 0 :
  A extends R['length'] ? never :
  B extends R['length'] ? GetLen<A, R> :
  Subtract<A, B, [...R, 0]>;

元祖中是否包含差值

求出每一項的差值後，需要判斷元組中是否存在，存在則滿足 被減數和減數 都存在元祖，作為復合條件的一組返回

  • 從元祖第一項開始遞歸至末尾，則返回false
  • 若某一項的值滿足尋找的值，返回ture，否則遞歸
type Includes<A extends number[], T extends number, L extends number[] = []> =
  A['length'] extends L['length'] ? false :
  A[L['length']] extends T ? true : Includes<A, T, [...L, 0]>;

遞歸元組

根據最開始的思路可以實現：

  • 依次遞歸元祖
  • 對每一項求差值
  • 判斷差值是否存在於數組中
  • R是返回的結果，N是遞歸計數，Item是被減數，SubItem是減數
type TwoSum<
  T extends number,
  L extends number[],
  R extends number[][] = [],
  N extends number[] = [],
  Item extends number = L[N['length']],
  SubItem extends number = Subtract<T, Item>,
> = L['length'] extends N['length'] ?
  R : TwoSum<
    T,
    L,
    Includes<L, SubItem> extends true ? [
      ...R,
      [Item, SubItem]
    ] : R,
    [...N, 0]
  >;
  
type t1 = TwoSum<4, [1, 2, 3]>;
// [[1, 3], [2, 2], [3, 1]]

存在缺陷：

  • 如果被減數和減數值相同，且隻存在一個，那結果也是滿足的。如：4 和 [1, 2, 3]，我們要的是 [1, 3]，需要排除掉 [2, 2]
  • 遞歸到被減數和減數都會滿足條件，會存在重復的兩個結果。如：4 和 [1, 2, 3]，我們要的是 [1, 3]，需要排除掉 [3, 1]

出現這兩個問題，是因為遞歸過的被減數仍然保留在元祖中，所以我們需要把遞歸過的被減數移除掉

優化一下：

  • 每次遞歸後移除當前項
type GetNext<T extends number[]> = T extends [number, ...infer U] ? U : [];

type TwoSum<
  T extends number,
  L extends number[],
  R extends number[][] = [],
  Item extends number = L[0],
  SubItem extends number = Subtract<T, Item>,
  NextL extends number[] = GetNext<L>,
> = L['length'] extends 0 ?
  R : TwoSum<
    T,
    NextL,
    Includes<NextL, SubItem> extends true ? [
      ...R,
      [Item, SubItem]
    ] : R
  >;

測試

type t1 = TwoSum<7, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]>;
// [[0, 7], [1, 6], [2, 5], [3, 4]]

type t2 = TwoSum<12, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]>;
// [[3, 9], [4, 8], [5, 7]]

type t3 = TwoSum<20, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]>;
// []

type t4 = TwoSum<10, [0, 8, 2, 1, 4, 7, 6, 3, 4, 9]>;
// [[8, 2], [1, 9], [4, 6], [7, 3], [6, 4]]

實現ThreeSum

實現排序

之前已經實現typescript的快排，移步：用typescript類型來實現快排

為什麼需要實現排序，因為上文中 TwoSum泛型的實現，需要滿足

  • 輸入參數 – 被減數 = 減數。所以 輸入參數 > 被減數 、 輸入參數 > 減數
  • 從頭選取參數、被減數、減數

所以排序後可以直接使用TwoSum泛型

實現ThreeSum

  • 遞歸元祖
  • 依次選擇 TwoSum的參數，剩餘元組
  • 剩餘元組中挑選符合條件的被減數、減數並返回
  • R為返回結果，NextL為剩餘元組，NewList為合並TwoSum的結果
// 合並參數到TwoSum的結果，因為TwoSum返回的二元數組
type GetNewList<
  A extends number,
  T extends number[][],
  N extends number[] = [],
  R extends number[][] = []
> = T['length'] extends N['length'] ? R :
  GetNewList<A, T, [...N, 0], [...R, [A, ...T[N['length']]]]>;

type IsArray<T> = T extends number[] ? T : [];

type IsArray2<T> = T extends number[][] ? T : [];

type ThreeSumLoop<
  L extends number[],
  R extends number[][] = [],
  NextL extends number[] = GetNext<L>,
  NewList extends number[][] = IsArray2<TwoSum<L[0], NextL>>
> = L['length'] extends 0 | 1 ? R :
  ThreeSumLoop<NextL, NewList['length'] extends 0 ? R :
  IsArray2<[...R, ...GetNewList<L[0], NewList>]>>;

type ThreeSum<L extends number[]> = ThreeSumLoop<IsArray<QuickSort<L>>>;

測試

type l1 = ThreeSum<[1, 3, 2, 4]>;
// [[4, 3, 1], [3, 2, 1]]

type l2 = ThreeSum<[1, 6, 3, 7, 5, 4, 2]>;
// [[7, 6, 1], [7, 5, 2], [7, 4, 3], [6, 5, 1], [6, 4, 2], [5, 4, 1], [5, 3, 2], [4, 3, 1], [3, 2, 1]]

type l3 = ThreeSum<[0, 5, 15, 10, 5, 25, 20]>;
// [[25, 20, 5], [25, 15, 10], [20, 15, 5], [15, 10, 5], [10, 5, 5], [5, 5, 0]]

type l4 = ThreeSum<[1, 16, 3, 17, 5, 4, 21]>;
// [[21, 17, 4], [21, 16, 5], [17, 16, 1], [5, 4, 1], [4, 3, 1]]

到此這篇關於使用typescript類型實現ThreeSum的文章就介紹到這瞭,更多相關typescript ThreeSum內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：