有效三角形的个数

[xszi]

给定一个包含非负整数的数组，你的任务是统计其中可以组成三角形三条边的三元组个数。

示例 1:

输入: [2,2,3,4]
输出: 3
解释:
有效的组合是: 
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3

注意:

• 数组长度不超过1000。
• 数组里整数的范围为 [0, 1000]。

[xszi]

排序+双指针

我们知道三角形的任意两边之和大于第三边，任意两边之差小于第三边，如果这三条边长从小到大为 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 是增序排列），继续判断

const count = (nums) => {
    let count = 0
    nums = nums.sort((a, b) => a - b)
    for (let j = nums.length - 1; j >= 2; j--) {
        // 确定最长边
        let left = 0,
            right = j - 1
        while (left < right) {
            if (nums[left] + nums[right] > nums[j]) {
                count += right - left
                right--
            } else {
                left++
            }
        }
    }
    return count
}

复杂度分析：

时间复杂度：O(n^2) 空间复杂度：O(n)