地址
leetcode地址：
难度
简单
题目
给定由一些正数（代表长度）组成的数组 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;
}
}