每日一题三角形周长题

地址

leetcode地址：

***/problems/largest-perimeter-triangle/description/?envType=study-plan-v2&envId=programming-skills

难度

简单

题目

给定由一些正数（代表长度）组成的数组 nums ，返回 由其中三个长度组成的、面积不为零的三角形的最大周长 。如果不能形成任何面积不为零的三角形，返回 0。

示例 1：

输入：nums = [2,1,2]

输出：5

解释：你可以用三个边长组成一个三角形:1 2 2。

示例 2：

输入：nums = [1,2,1,10]

输出：0

解释：

你不能用边长 1,1,2 来组成三角形。

不能用边长 1,1,10 来构成三角形。

不能用边长 1、2 和 10 来构成三角形。

因为我们不能用任何三条边长来构成一个非零面积的三角形，所以我们返回 0

提示：

• 3 <= nums.length <= 10^4
• 1 <= nums[i] <= 10^6

思路

判断是否可以组成三角形，即任意两边相加大于第三边。本题最简单粗暴的办法就是使用三个for循环，循环判断nums数组中的数值是否可以组成三角形，将组成的三角形的周长去最大值

class Solution { public int largestPerimeter(int[] nums) { int result = 0; int temp =0; // 循环判断遍历，满足组成三角形的条件，则求其周长 for(int i =0;i<nums.length-2;i++){ for(int j =i+1;j< nums.length-1;j++){ for(int z = j+1;z< nums.length;z++){ if((nums[i] + nums[j] > nums[z]) && (nums[i] + nums[z] > nums[j]) && (nums[z] + nums[j] > nums[i])){ temp = nums[i] + nums[j] + nums[z]; } result = Math.max(result,temp); } } } return result; }}

不过上述代码逻辑上是没有问题，但去执行的时候，不出意外会直接提示超时时间限制。在算法编写中，基本上不会使用三层for循环的。

在返回来看题目，题目的要求是求三角形的最大周长。数组中要是可以组成最大的三角形周长，即这三个数是数组中最大的数值。即可以先对数组进行排序，排序完成之后，从最后三个数开始进行三角形。如果组成三角形成功，则这三个数组成的三角形周长最大。

class Solution { public int largestPerimeter(int[] nums) { // 对数组进行排序 Arrays.sort(nums); for (int i =nums.length-1;i>=2;i--) { int a = nums[i]; int b = nums[i-1]; int c = nums[i-2]; if ((a + b > c) && (c + b > a) && (a + c > b)) { return a + b + c; } } return 0; }}

对上述代码可进行优化,使其时间消耗更低.

class Solution { public int largestPerimeter(int[] nums) { int a = getMax(nums); int b = getMax(nums); for(int i=2;i<nums.length;i++){ int c = getMax(nums); if((b+c)>a){ return a+b+c; } else { a = b; b = c; } } return 0; } int getMax(int[] nums){ int max = -1; int maxI = 0; for(int i=0;i<nums.length;i++){ if(max < nums[i]){ max = nums[i]; maxI = i; } } nums[maxI] = -1; return max; }}