---
# System prepended metadata

title: 976. Largest Perimeter Triangle
tags: [math, Leetcode, greedy, python, array, c++, sort, easy]

---

###### tags: `Leetcode` `easy` `array` `math` `greedy` `sort` `python` `c++`

# 976. Largest Perimeter Triangle

## [題目連結:] https://leetcode.com/problems/largest-perimeter-triangle/description/

## 題目:
Given an integer array ```nums```, return the largest perimeter of a triangle with a non-zero area, formed from three of these lengths. If it is impossible to form any triangle of a non-zero area, return ```0```.

**Example 1:**
```
Input: nums = [2,1,2]
Output: 5
```
**Example 2:**
```
Input: nums = [1,2,1]
Output: 0
```

## 解題想法:
* 此題為數組中求出能構成三角形的最長邊長
* 三角形:
    * 任兩邊和>第三邊
    * **兩短邊和>第三邊**
        * 先排序好
        * 判斷尾巴最長三邊的關係即可

## Python:
``` python=
class Solution(object):
    def largestPerimeter(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        #兩邊和大於第三邊
        #排序好判斷最尾三個
        n=len(nums)
        nums.sort()
        first=n-3
        second=n-2
        third=n-1
        while first>=0:
            if (nums[first]+nums[second]>nums[third]):
                return nums[first]+nums[second]+nums[third]
            first-=1
            second-=1
            third-=1
        return 0
```

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