有效三角形的个数-贪心

题目

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

示例

输入: nums = [4,2,3,4]
输出: 4

算法

先排序
对于每一个确定的nums[i]点，从它的前面找出能组成三角形的两个点
left = 0, right = i - 1；
如果此时可以组成三角形(nums[left] + num[right] > nums[i])，则nums[left] ~num[right-1]都可以与num[right]和nums[i]组成三角形
res += right - left; right–
如果此时不行，则left++

代码

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