976-三角形的最大周长

给定由一些正数（代表长度）组成的数组 nums ，返回 由其中三个长度组成的、面积不为零的三角形的最大周长 。如果不能形成任何面积不为零的三角形，返回 0。

 

示例 1：

输入：nums = [2,1,2]
输出：5
示例 2：

输入：nums = [1,2,1]
输出：0
 

提示：

3 <= nums.length <= 104
1 <= nums[i] <= 106

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/largest-perimeter-triangle
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

组成三角形的三条边之间需要满足如下条件：

• 任意两边之和大于第三边
• 任意两边之差小于第三边

假设a b c为三边，则需要以下不等式均成立。

• Math.abs(a - b) < c

• Math.abs(a - c) < b

• Math.abs(b - c) < a

• a + b > c

• a + c > b

• b + c > a

我们考虑 a b c三者中最小值为a，最大值为c，中间值为b，以下六个不等式可以进行优化。

• Math.abs(a - b) < c c为最大值，一定成立

• Math.abs(a - c) < b 因为a < c，等价于 c - a > b

• Math.abs(b - c) < a 因为b < c，等价于 c - b > a

• a + b > c

• a + c > b 一定成立

• b + c > a 一定成立

根据上面的分析，我们可以将不等式简化为三条：

• c - a > b
• c - b > a
• a + b > c

我们发现，上面三条实际就是一条。

• a + b > c

所以，我们可以先将数组进行排序，然后判断出三个边中的最大值、最小值、中间值，满足上面不等式的 即为所求解。

   public int largestPerimeter(int[] nums) {
        Arrays.sort(nums);
        int length = nums.length;
        //循环我们从最大值一侧开始，这样得到第一组符合条件的解后即为答案
        for (int i = length - 1 ; i >= 0  ; i--) {
            int max = nums[i];
            for (int j = i-1; j >= 0 ; j--) {
                int middle = nums[j];
                for (int k = j-1; k >= 0 ; k--) {
                    int min = nums[k];
                    if (min + middle > max) {
                        return middle + max + min;
                    }

                }
            }
        }
        return 0;
    }