日常算法：有效三角形个数

本文转载自微信公众号《三分钟学前端》，作者安姐。转载本文请联系三分钟学习前端公众号。给定一个包含非负整数的数组，您的任务是计算可以构成三角形三边的三元组的数量。示例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向前移动一个bit(j--)，继续进入下一轮判断nums[i]+nums[j]<=nums[k]，然后将l向后移动一位（nums为升序），继续判断代码实现：lettriangleNumber=function(nums){if(!nums||nums.length<3)return0letcount=0//排序nums.sort((a,b)=>a-b)for(letk=nums.length-1;k>1;k--){leti=0,j=k-1while(inums[k]){count+=j-ij--}埃尔斯e{i++}}}returncount}复杂度分析：时间复杂度：O(n^2^)空间复杂度：O(n)注意：关于Array.prototype.sort()，ES规范没有规定具体的算法。在V8引擎中，7.0版本之前，当数组长度小于10时，Array.prototype.sort()使用插入排序，否则使用快速排序。Quicksort在V8引擎7.0版本后被废弃，因为它不是一个稳定的排序算法，在最坏的情况下，时间复杂度会降低到O(n2)。相反，使用混合排序算法：TimSort。这种函数式算法最初是在Python语言中使用的。严格来说，它不属于以上10种排序算法中的任何一种。属于混合排序算法：在数据量较小的子数组中使用插入排序，然后使用Merge排序对有序的子数组进行合并排序，时间复杂度为O(nlogn)。leetcode:https://leetcode-cn.com/problems/valid-triangle-number/solution/teng-xun-leetcode611you-xiao-san-jiao-xing-de-ge-s/