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:

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

Solution(javascript)

/** 类似 611, O(n^2)，还可以有 O(n) 的解法
 * @param {number[]} A
 * @return {number}
 */
// const largestPerimeter = function (A = []) {
//   A.sort((a, b) => b - a)
//   for (let i = 0; i < A.length - 2; i++) {
//     for (let j = i + 1; j < A.length - 1; j++) {
//       const k = j + 1
//       const a = A[i]
//       const b = A[j]
//       const c = A[k]
//       if (b + c > a) {
//         return a + b + c
//       }
//     }
//   }
//   return 0
// }

// O(n)
const largestPerimeter = function (A = []) {
  A.sort((a, b) => b - a)
  for (let i = 0; i < A.length - 2; i++) {
    if (A[i] < A[i + 1] + A[i + 2]) {
      return A[i] + A[i + 1] + A[i + 2]
    }
  }
  return 0
}