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

╰+哭是因爲堅強的太久メ 2022-09-03 01:19 183阅读 0赞

## 题目链接 ##

[611. 有效三角形的个数][611.]

## 题目简介 ##

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

示例 1:

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

**注意:**

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

## 题目解析 ##

1.  第一次看见这个题目，脑海中第一个想法就是直接进行三次循环，进行判断，时间复杂度O(N^3)
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 - 1`
        
         *  如果当前的 `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;
        }
    }

[611.]: https://leetcode-cn.com/problems/valid-triangle-number/