【力扣每日一题：8-04】611. 有效三角形的个数【中等】

题目链接

611. 有效三角形的个数

题目简介

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

示例 1:

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

注意:

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

题目解析

1. 1.第一次看见这个题目，脑海中第一个想法就是直接进行三次循环，进行判断，时间复杂度O(N^3)
2. 2.优化成O(N^2)的做法：

• 先进行排序，Arrays.sort(nums);
• 我们看一下关于三角形的定义：

• x + y > z && x + z > y && y + z > x
• 我们将外循环的定义成：for(int i = nums.length - 1; i >= 2; i--){}，将外循环看做 z
• 利用双指针 int left = 0，int right = i -
• 如果当前的 nums[left] + nums[right] > z 的话，证明我们左边界取 left ~ right - 1 的数据都可以形成一个三角形
• 如果 nums[left] + nums[right] < z 的话，证明当前的 left 太小，需要向右进行调整。

• 最终返回结果即可

题目代码

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