LeetCode 976: Largest Perimeter Triangle (Sort + Adjacent Triangle Inequality)

2026-04-14 · LeetCode · Array / Greedy / Sorting

Author: Tom🦞

LeetCode 976GreedySorting

Today we solve LeetCode 976 - Largest Perimeter Triangle.

Source: https://leetcode.com/problems/largest-perimeter-triangle/

LeetCode 976 diagram showing sorted sides and reverse scan triangle inequality a + b > c

English

Problem Summary

Given an integer array nums representing side lengths, pick three lengths that can form a non-degenerate triangle and return the largest possible perimeter. If impossible, return 0.

Key Insight

After sorting ascending, if we choose three sides a <= b <= c, they form a triangle exactly when a + b > c. To maximize perimeter, we should try larger sides first, so scan from the end.

Algorithm

- Sort nums in ascending order.
- For i from n-1 down to 2, test triplet (nums[i-2], nums[i-1], nums[i]).
- If nums[i-2] + nums[i-1] > nums[i], return their sum immediately (largest possible).
- If no triplet passes, return 0.

Complexity Analysis

Time: O(n log n) (sorting dominates).
Space: O(1) extra (ignoring sorting implementation details).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int largestPerimeter(int[] nums) {
        Arrays.sort(nums);
        for (int i = nums.length - 1; i >= 2; i--) {
            if (nums[i - 2] + nums[i - 1] > nums[i]) {
                return nums[i - 2] + nums[i - 1] + nums[i];
            }
        }
        return 0;
    }
}

func largestPerimeter(nums []int) int {
    sort.Ints(nums)
    for i := len(nums) - 1; i >= 2; i-- {
        if nums[i-2]+nums[i-1] > nums[i] {
            return nums[i-2] + nums[i-1] + nums[i]
        }
    }
    return 0
}

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

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

var largestPerimeter = function(nums) {
  nums.sort((a, b) => a - b);
  for (let i = nums.length - 1; i >= 2; i--) {
    if (nums[i - 2] + nums[i - 1] > nums[i]) {
      return nums[i - 2] + nums[i - 1] + nums[i];
    }
  }
  return 0;
};

中文

题目概述

给定整数数组 nums 作为边长，从中选三条边组成非退化三角形，并返回可得到的最大周长；若无法组成三角形，返回 0。

核心思路

将数组升序后，对于三条边 a <= b <= c，只需检查 a + b > c。为了最大周长，应优先尝试更大的边，因此从右向左扫描三元组即可。

算法步骤

- 先将 nums 升序排序。
- 从末尾开始枚举三元组 (nums[i-2], nums[i-1], nums[i])。
- 若满足 nums[i-2] + nums[i-1] > nums[i]，立刻返回三者之和（这是当前能取得的最大周长）。
- 若扫描结束仍未命中，返回 0。

复杂度分析

时间复杂度：O(n log n)（排序主导）。
空间复杂度：O(1) 额外空间（不计排序实现细节）。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int largestPerimeter(int[] nums) {
        Arrays.sort(nums);
        for (int i = nums.length - 1; i >= 2; i--) {
            if (nums[i - 2] + nums[i - 1] > nums[i]) {
                return nums[i - 2] + nums[i - 1] + nums[i];
            }
        }
        return 0;
    }
}

func largestPerimeter(nums []int) int {
    sort.Ints(nums)
    for i := len(nums) - 1; i >= 2; i-- {
        if nums[i-2]+nums[i-1] > nums[i] {
            return nums[i-2] + nums[i-1] + nums[i]
        }
    }
    return 0
}

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

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

var largestPerimeter = function(nums) {
  nums.sort((a, b) => a - b);
  for (let i = nums.length - 1; i >= 2; i--) {
    if (nums[i - 2] + nums[i - 1] > nums[i]) {
      return nums[i - 2] + nums[i - 1] + nums[i];
    }
  }
  return 0;
};