Question

Formatted question description: https://leetcode.ca/all/976.html

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 <= 10000
1 <= A[i] <= 10^6

Algorithm

Since we want to form a triangle, we must satisfy the property that the sum of the two sides is greater than the third side. We do not need to detect all combinations, but only need to judge whether the sum of the shorter sides is greater than the longest side. Although this is an Easy topic, OJ still does not allow brute force search methods, and traversing any three edges will time out.

So we can only think of an optimized solution. Since the longest circumference is required, it is definitely better to choose a larger number to test first. Here, we will sort the array first, then start from the end, take out three numbers each time, first check whether a triangle can be formed, if possible, return the perimeter directly, if not, continue to take forward, if not, return 0, see the code as follows:

Code

C++

class Solution {
public:
    int largestPerimeter(vector<int>& A) {
        sort(A.begin(), A.end());
        for (int i = (int)A.size() - 1; i >= 2; --i) {
            if (A[i] < A[i - 1] + A[i - 2]) {
                return A[i] + A[i - 1] + A[i - 2];
            }
        }
        return 0;
    }
};

All Problems

All Solutions