[[429712]]

本文轉載自微信公眾號「三分鐘學前端」，作者sisterAn。轉載本文請聯(lián)系三分鐘學前端公眾號。

給定一個包含非負整數的數組，你的任務是統(tǒng)計其中可以組成三角形三條邊的三元組個數。

示例 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-- )， 繼續(xù)進入下一輪判斷

• nums[i] + nums[j] <= nums[k]，則 l 往后移動一位(nums 是增序排列)，繼續(xù)判斷

代碼實現(xiàn)：

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 規(guī)范并沒有指定具體的算法，在 V8 引擎中， 7.0 版本之前，數組長度小于10時， Array.prototype.sort() 使用的是插入排序，否則用快速排序。

在 V8 引擎 7.0 版本之后就舍棄了快速排序，因為它不是穩(wěn)定的排序算法，在最壞情況下，時間復雜度會降級到 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/