LeetCode976. 三角形的最大周长-Java&Go-排序&数学

• 算法
  • 1.排序
  • 2.对于三个数 a > b > c，只要有 a < b + c 即可组成三角形
    • 因为 a > b > c，所以 a + b > c && a + c > b
    • 加上 b + c > a，所以 a b c可以组成三角形
  • 3.排完序之后从大到小依次检查三个数即可

public int largestPerimeter(int[] A) {
    if (A == null || A.length < 3) {
        return 0;
    }

    A = IntStream.of(A)
            .boxed()
            .sorted(Collections.reverseOrder())
            .mapToInt(Integer::intValue)
            .toArray();
    for (int 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;
}

public int largestPerimeter(int[] A) {
    if (A == null || A.length < 3) {
        return 0;
    }

    Arrays.sort(A);
    for (int i = A.length - 1; i >= 2; i--) {
        if (A[i] < A[i-1] + A[i-2]) {
            return A[i] + A[i-1] + A[i-2];
        }
    }
    return 0;
}

func largestPerimeter(A []int) int {
    if A == nil || len(A) < 3 {
        return 0
    }

    sort.Ints(A)
    for i := len(A) - 1; i >= 2; i-- {
        if A[i] < A[i-1] + A[i-2] {
            return A[i] + A[i-1] + A[i-2]
        }
    }
    return 0
}