976-三角形的最大周长（Largest Perimeter Triangle）

男娘i 2022-01-26 06:15 193阅读 0赞

**题目描述**  
**中文：**  
给定由一些正数（代表长度）组成的数组 A，返回由其中三个长度组成的、面积不为零的三角形的最大周长。

如果不能形成任何面积不为零的三角形，返回 0。  
**英文：**  
Given an array A of positive lengths, return the largest perimeter of a triangle with non-zero area, formed from 3 of these lengths.

If it is impossible to form any triangle of non-zero area, return 0.

**示例：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpMTM3NjQxNzUzOQ_size_16_color_FFFFFF_t_70]  
**提示：**

3 <= A.length <= 10000
    	1 <= A[i] <= 10^6

**题目分析**  
1.首先我们最粗暴直接的想到的就是三层循环暴力破解，求出最大的周长值

class Solution {
        public int largestPerimeter(int[] A) {
            int len = A.length;
            int max = 0;
            for(int i = 0;i<len;i++)
                for(int j = i + 1;j < len; j++)
                    for(int k = j + 1; k < len; k++){
                        if(canDo(A[i],A[j],A[k]))
                            if(max < A[i] + A[j] + A[k])			//不断更新max的值
                                max = A[i] + A[j] + A[k];
                    }
            return max;
        }
        public boolean canDo(int a,int b,int c){		//判断是否能构成三角形
           return a + b > c && a + c > b && c + b > a;
        }
    }

2.很明显，上述方法的时间复杂度为O(N^3)，时间性能十分糟糕那么我们如何对其进行必要的优化呢。

题目要求我们要返回的是一个最大的周长，那我们很容易想到的就是先将数组排序，然后从最大的开始找，如果找到就直接返回

Arrays.sort(A);
    for(int i = len - 3;i >= 0;i--)
                if(A[i] + A[i+1] > A[i+2])                  //两条小边加起来大于最大边，则能构成三角形
                    return A[i] + A[i+1] + A[i+2];

那为什么我们这里只用了一层循环和一个判断呢？
    	如果三条最大的边 A[len-1],A[len-2],A[len-3] 不能构成三角形，即A[len-1] > A[len-2] + A[len-3] 那么第一条
    	A[len - 1]一定不能成为三角形中的一条边，同理其他两条边再往后搜索也就没了意义。

好了，这是一道十分简单的题目，分析到这里我们就可以写出他的题解了。  
**Java代码**

class Solution {
        public int largestPerimeter(int[] A) {
            int len = A.length;
            Arrays.sort(A);
            for(int i = len - 3;i >= 0;i--)
                if(A[i] + A[i+1] > A[i+2])                  //两条小边加起来大于最大边，则能构成三角形
                    return A[i] + A[i+1] + A[i+2];
            return 0;
        }
    }

**Python3代码**

class Solution:
        def largestPerimeter(self, A: List[int]):
            A.sort(reverse = True)
            l = len(A)
            for i in range(l-2):
                if A[i+1] + A[i+2] > A[i]:
                    return A[i] + A[i+1] + A[i+2]
            return 0

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpMTM3NjQxNzUzOQ_size_16_color_FFFFFF_t_70]: /images/20220126/d1598b24c3d84d1e9a669a780eb20658.png