前往
大廳
主題

LeetCode - 1534. Count Good Triplets 解題心得

Not In My Back Yard | 2021-07-06 00:00:01 | 巴幣 0 | 人氣 252

題目連結:


題目意譯:
給定一整數陣列 arr 以及三個整數 a 、 b 和 c 。你需要找到好三元數組的數量。

一個三元數組 (arr[i], arr[j], arr[k]) 是好的如果下列條件為真:
0 ≦ i < j < k < arr.length
|arr[i] - arr[j]| <= a
|arr[j] - arr[k]| <= b
|arr[i] - arr[k]| <= c
其中 |x| 代表著 x 的絕對值。

回傳好三元數組的數目。

限制:
3 ≦ arr.length ≦ 100
0 ≦ arr[i] ≦ 1000
0 ≦ a 、 b 、 c ≦ 1000



範例測資:
範例 1:
輸入: arr = [3,0,1,1,9,7], a = 7, b = 2, c = 3
輸出: 4
解釋: 這裡有著 4 個好三元數組:[(3,0,1), (3,0,1), (3,1,1), (0,1,1)]。

範例 2:
輸入: arr = [1,1,2,2,3], a = 0, b = 0, c = 1
輸出: 0
解釋: 沒有三元數組滿足所有條件。


解題思維:
窮舉即可。直接用三層的迴圈產生出所有 (i, j, k) 三元數組,其中 0 ≦ i < j < k < arr.length 。

因此可以看到每組 (i, j, k) 對應到一組 (arr[i], arr[j], arr[k]) ,然後直接判斷每個窮舉出來的數組是否符合題目所要求的條件。每符合一組,負責計數的變數 C (初始值為 0)就加 1。

最後窮舉完後的 C 值即是所求。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作