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

Activity

1. sisterAn

   added

   腾讯

   LeetCode

   on Aug 10, 2020
2. sisterAn commented on Aug 10, 2020

   

   sisterAn

   on Aug 10, 2020

   Last edited by sisterAn

   OwnerAuthor

   More actions

   本题可结合:

   • 字节&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
3. chenzesam commented on Aug 11, 2020

   

   chenzesam

   on Aug 11, 2020

   Last edited by chenzesam

   More actions

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

   😕React with 😕1Reacted by Stephan_zhang
4. Glittergalaxy commented on Aug 11, 2020

   

   Glittergalaxy

   on Aug 11, 2020

   More actions

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

   判定公式是 任意两边之和大于第三边
5. xuanweiH commented on Nov 1, 2020

   

   xuanweiH

   on Nov 1, 2020

   More actions

   count+=1 吧 怎么会是count += j-1
6. wcora commented on Nov 9, 2020

   

   wcora

   on Nov 9, 2020

   More actions

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

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

   

   xuanweiH

   on Nov 10, 2020

   More actions

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

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

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