快捷導(dǎo)航

使用typescript類型實(shí)現(xiàn)ThreeSum

更新時(shí)間：2022年08月14日 10:14:30 作者：東東么么噠

這篇文章主要介紹了使用typescript類型實(shí)現(xiàn)ThreeSum，文章圍繞主題展開詳細(xì)的內(nèi)容介紹，具有一定的參考價(jià)值，需要的小伙伴可以一下，希望對(duì)你學(xué)習(xí)又是幫助

前言

本文執(zhí)行環(huán)境typescript，版本4.7.4

不使用typescript的計(jì)算能力，通過(guò)類型來(lái)實(shí)現(xiàn)ThreeSum

思路整理

實(shí)現(xiàn)ThreeSum之前我們先降低下難度，實(shí)現(xiàn)TwoSum，因?yàn)門woSum可以作為ThreeSum的基礎(chǔ)泛型

TwoSum需要準(zhǔn)備什么呢？

遞歸元組，模擬for循環(huán)
減法，遞歸過(guò)程中求出差值
對(duì)每一項(xiàng)差值判斷是否存在

完成TwoSum后如何實(shí)現(xiàn)ThreeSum？

每一項(xiàng)和剩余元組走一遍 TwoSum泛型，篩選滿足條件的
為了保證每一項(xiàng)能夠走TwoSum泛型，對(duì)于元組大到小排序

實(shí)現(xiàn)TwoSum

實(shí)現(xiàn)減法

因?yàn)樵M下標(biāo)是遞增有序數(shù)列，我們?cè)诿看芜f歸的時(shí)候返回一個(gè)長(zhǎng)度+1的新元組并獲取長(zhǎng)度，就可以對(duì)非負(fù)整數(shù)依次點(diǎn)名了

如求A - B，我們假設(shè)A - B永遠(yuǎn)是非負(fù)整數(shù)數(shù)，無(wú)限遞歸產(chǎn)生新元祖的過(guò)程中，排查掉A和B相等后，必定是先點(diǎn)名到B，然后點(diǎn)名到A，而B 到 A的遞歸次數(shù)就是差值，也就是求得的結(jié)果

實(shí)現(xiàn)這個(gè)差值的計(jì)算

A作為被減數(shù)，R作為長(zhǎng)度與減數(shù)相等的數(shù)組，Z則用于遞歸累增
當(dāng)被減數(shù)R長(zhǎng)度等于A的過(guò)程中，Z則是被減數(shù)和減數(shù)的差值

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]>;

元祖中是否包含差值

求出每一項(xiàng)的差值后，需要判斷元組中是否存在，存在則滿足被減數(shù)和減數(shù) 都存在元祖，作為復(fù)合條件的一組返回

從元祖第一項(xiàng)開始遞歸至末尾，則返回false
若某一項(xiàng)的值滿足尋找的值，返回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]>;

遞歸元組

根據(jù)最開始的思路可以實(shí)現(xiàn)：

依次遞歸元祖
對(duì)每一項(xiàng)求差值
判斷差值是否存在于數(shù)組中
R是返回的結(jié)果，N是遞歸計(jì)數(shù)，Item是被減數(shù)，SubItem是減數(shù)

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]]

存在缺陷：

如果被減數(shù)和減數(shù)值相同，且只存在一個(gè)，那結(jié)果也是滿足的。如：4 和 [1, 2, 3]，我們要的是 [1, 3]，需要排除掉 [2, 2]
遞歸到被減數(shù)和減數(shù)都會(huì)滿足條件，會(huì)存在重復(fù)的兩個(gè)結(jié)果。如：4 和 [1, 2, 3]，我們要的是 [1, 3]，需要排除掉 [3, 1]

出現(xiàn)這兩個(gè)問(wèn)題，是因?yàn)檫f歸過(guò)的被減數(shù)仍然保留在元祖中，所以我們需要把遞歸過(guò)的被減數(shù)移除掉

優(yōu)化一下：

每次遞歸后移除當(dāng)前項(xiàng)

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
  >;

測(cè)試

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]]

實(shí)現(xiàn)ThreeSum

實(shí)現(xiàn)排序

之前已經(jīng)實(shí)現(xiàn)typescript的快排，移步：用typescript類型來(lái)實(shí)現(xiàn)快排

為什么需要實(shí)現(xiàn)排序，因?yàn)樯衔闹?TwoSum泛型的實(shí)現(xiàn)，需要滿足

輸入?yún)?shù) - 被減數(shù) = 減數(shù)。所以輸入?yún)?shù) > 被減數(shù) 、輸入?yún)?shù) > 減數(shù)
從頭選取參數(shù)、被減數(shù)、減數(shù)

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

實(shí)現(xiàn)ThreeSum

遞歸元祖
依次選擇 TwoSum的參數(shù)，剩余元組
剩余元組中挑選符合條件的被減數(shù)、減數(shù)并返回
R為返回結(jié)果，NextL為剩余元組，NewList為合并TwoSum的結(jié)果

// 合并參數(shù)到TwoSum的結(jié)果，因?yàn)門woSum返回的二元數(shù)組
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>>>;

測(cè)試

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]]

到此這篇關(guān)于使用typescript類型實(shí)現(xiàn)ThreeSum的文章就介紹到這了,更多相關(guān)typescript ThreeSum內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: