[leetcode] 976. Largest Perimeter Triangle

Description

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.

Example 1:

Input: [2,1,2]
Output: 5

Example 2:

Input: [1,2,1]
Output: 0

Example 3:

Input: [3,2,3,4]
Output: 10

Example 4:

Input: [3,6,2,3]
Output: 8

Note:

3 <= A.length <= 100001 <= A[i] <= 10^6分析

题目的意思是：求给定数组构成的最大三角形的周长。我最开始写了三重循环暴力破解了一下，发现超时了。后面发现只需要排序然后从后往前找第一个符合三角形（两边之和大于第3边）要求的就是结果了。

代码

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

参考文献

​​solution​​