每日算法：有效三角形的個數
本文轉載自微信公眾號「三分鐘學前端」，作者sisterAn。轉載本文請聯系三分鐘學前端公眾號。
給定一個包含非負整數的數組，你的任務是統計其中可以組成三角形三條邊的三元組個數。
示例 1:
- 輸入: [2,2,3,4]
- 輸出: 3
- 解釋:
- 有效的組合是:
- 2,3,4 (使用第一個 2)
- 2,3,4 (使用第二個 2)
- 2,2,3
注意:
- 數組長度不超過1000。
- 數組里整數的范圍為 [0, 1000]。
解法：排序+雙指針
我們知道三角形的任意兩邊之和大于第三邊，任意兩邊之差小于第三邊，如果這三條邊長從小到大為 a 、 b 、 c ，當且僅當 a + b > c 這三條邊能組成三角形
解題思路： 先數組排序，排序完后，固定最長的邊，利用雙指針法判斷其余邊
以 nums[nums.length - 1] 作為最長的邊 nums[k] ( k = nums.length - 1 )
以 nums[i] 作為最短邊，以 nums[nums.length - 2] 作為第二個數 nums[j] ( j = nums.length - 2 ) ，
判斷 nums[i] + nums[j] 是否大于 nums[k] ，
- nums[i] + nums[j] > nums[k] ，則：
- nums[i+1] + nums[j] > nums[k]
- nums[i+2] + nums[j] > nums[k]
- ...
- nums[j-1] + nums[j] > nums[k]
則可構成三角形的三元組個數加 j-i ，并且 j 往前移動一位( j-- )， 繼續進入下一輪判斷
- nums[i] + nums[j] <= nums[k]，則 l 往后移動一位(nums 是增序排列)，繼續判斷
代碼實現：
- let triangleNumber = function(nums) {
- if(!nums || nums.length < 3) return 0
- let count = 0
- // 排序
- nums.sort((a, b) => a - b)
- for(let k = nums.length - 1; k > 1; k--){
- let i = 0, j = k - 1
- while(i < j){
- if(nums[i] + nums[j] > nums[k]){
- count += j - i
- j--
- } else {
- i++
- }
- }
- }
- return count
- }
復雜度分析：
- 時間復雜度：O(n^2^)
- 空間復雜度：O(n)
注意：
關于 Array.prototype.sort() ，ES 規范并沒有指定具體的算法，在 V8 引擎中， 7.0 版本之前，數組長度小于10時， Array.prototype.sort() 使用的是插入排序，否則用快速排序。
在 V8 引擎 7.0 版本之后就舍棄了快速排序，因為它不是穩定的排序算法，在最壞情況下，時間復雜度會降級到 O(n2)。
而是采用了一種混合排序的算法：TimSort 。
這種功能算法最初用于Python語言中，嚴格地說它不屬于以上10種排序算法中的任何一種，屬于一種混合排序算法：
在數據量小的子數組中使用插入排序，然后再使用歸并排序將有序的子數組進行合并排序，時間復雜度為 O(nlogn) 。
leetcode：https://leetcode-cn.com/problems/valid-triangle-number/solution/teng-xun-leetcode611you-xiao-san-jiao-xing-de-ge-s/
