腾讯&leetcode611：有效三角形的个数

[sisterAn]

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

示例 1:

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

注意:

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

附赠leetcode地址：leetcode

[sisterAn]

本题可结合:

• 字节&leetcode1：两数之和
• 腾讯&leetcode15：三数之和

一起练习

解法：排序+双指针

我们知道三角形的任意两边之和大于第三边，任意两边之差小于第三边，如果这三条边长从小到大为 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(n²)。

而是采用了一种混合排序的算法：TimSort 。

这种功能算法最初用于Python语言中，严格地说它不属于以上10种排序算法中的任何一种，属于一种混合排序算法：

在数据量小的子数组中使用插入排序，然后再使用归并排序将有序的子数组进行合并排序，时间复杂度为 O(nlogn) 。

leetcode

[chenzesam]

这个题目和三数之和雷同吧，只是将 a + b = c 的判定公式改成 a² + b² = c²。

[Glittergalaxy]

这个题目和三数之和雷同吧，只是将 a + b = c 的判定公式改成 a² + b² = c²。

判定公式是 任意两边之和大于第三边

[xuanweiH]

count+=1 吧 怎么会是count += j-1

[wcora]

count+=1 吧 怎么会是count += j-1

就是+= j - i，因为num[j] + num[i]足够大了，所以从 num[i] 到 num[j-1] 的数字 加上 num[j] 都可以符合条件
因为只要i够大右边j的bound是每轮都会变的，所以不会数重复

[xuanweiH]

count+=1 吧 怎么会是count += j-1

就是+= j - i，因为num[j] + num[i]足够大了，所以从 num[i] 到 num[j-1] 的数字 加上 num[j] 都可以符合条件
因为只要i够大右边j的bound是每轮都会变的，所以不会数重复

感谢, 确实如此 之前看错了