主題

LeetCode - 611. Valid Triangle Number 解題心得

Not In My Back Yard | 2021-11-25 00:00:01 | 巴幣 0 | 人氣 91

題目連結:


題目意譯:
給定一個整數陣列 nums,回傳如果我們將數字視為三角形之邊長,我們可以從陣列中選出數字組成一個三角形之三元組數量。

限制:
1 ≦ nums.length ≦ 1000
0 ≦ nums[i] ≦ 1000



範例測資:
範例 1:
輸入: nums = [2,2,3,4]
輸出: 3
解釋: 合法組合為:
2,3,4 (使用第一個 2)
2,3,4 (使用第二個 2)
2,2,3

範例 2:
輸入: nums = [4,2,3,4]
輸出: 4


解題思維:
首先我們將 nums 按照大小由小排到大。

接著我們從 i = 2 開始一路跑到 i = nums.length - 1(nums 索引值從 0 開始)。對於每個 i 值,我們執行以下程序:
我們定義兩個變數 L = 0 以及 U = i - 1。重複以下步驟直到 L ≧ U 為止。

可以看到當 nums[L] + nums[U] > nums[i] 時,代表我們找到了一個三元組 (nums[L], nums[U], nums[i]) 可以形成三角形之三邊長(兩個較短邊總和大於最長邊為三角形的充分必要條件)。同時也代表著 nums[L + 1] + nums[U] 、 nums[L + 2] + nums[U] 、……同樣也會大於 nums[i](因為先前的排序使得 nums[L] ≦ nums[L + 1] ≦ nums[L + 2] ≦……)。而這樣的三元組總共有 U - L 個。且因為 nums[U] 所有的可能配對已經用完了,因此我們將 U 減去 1。

而當 nums[L] + nums[U] ≦ nums[i] 時,代表三元組 (nums[L], nums[U], nums[i]) 不能形成三角形。因此我們將 L 加上 1,使其更有可能形成三角形。



而所求三元組之數量即是過程中所有 (U - L) 之值的總和。




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

創作回應

相關創作

更多創作