题目链接 有效三角形的个数

给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。

示例 1:

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

问题分析

暴⼒求解（会超时）：算法思路
三层 for 循环枚举出所有的三元组，并且判断是否能构成三⻆形。

判断三⻆形的优化：
▪ 如果能构成三⻆形，需要满⾜任意两边之和要⼤于第三边。但是实际上只需让较⼩的两条边之和⼤于第三边即可。
▪ 因此我们可以先将原数组排序，然后从⼩到⼤枚举三元组，⼀⽅⾯省去枚举的数量，另⼀⽅⾯⽅便判断是否能构成三⻆形。

排序+双指针：
先将数组排序。
我们可以固定⼀个「最⻓边」，然后在⽐这条边⼩的有序数组中找出⼀个⼆元组，使这个⼆元组之和⼤于这个最⻓边。由于数组是有序的，我们可以利⽤「对撞指针」来优化。
设最⻓边枚举到 i 位置，区间 [left, right] 是 i 位置左边的区间（也就是⽐它⼩的区间）：
▪ 如果 nums[left] + nums[right] > nums[i] ：
▪ 说明 [left, right - 1] 区间上的所有元素均可以与 nums[right] 构成⽐nums[i] ⼤的⼆元组
▪ 满⾜条件的有 right - left 种
▪ 此时 right 位置的元素的所有情况相当于全部考虑完毕， right-- ，进⼊下⼀轮判断
▪ 如果 nums[left] + nums[right] <= nums[i] ：
▪ 说明 left 位置的元素是不可能与 [left + 1, right] 位置上的元素构成满⾜条件
的⼆元组
▪ left 位置的元素可以舍去， left++ 进⼊下轮循环

代码解决

class Solution {public int triangleNumber(int[] nums) {Arrays.sort(nums);int r = 0;for(int i = nums.length-1;i>1;i--){int left = 0,right = i-1;while(left<right){if(nums[left]+nums[right]>nums[i]){r += right-left;right--;}else left++;}}return r;}
}

执行用时