Preface explains
Algorithm learning, daily brush record.
Subject to connect
The maximum perimeter of a triangle
The subject content
Given an array A of positive numbers (representing lengths), return the maximum perimeter of A non-zero triangle made up of three of these lengths.
If you cannot form any triangle with non-zero area, return 0.
Example 1:
Input:,1,2 [2]
Output: 5
Example 2:
Input: [1, 2, 1]
Output: 0
Example 3:
Input: [3, 2, 3, 4]
Output: 10
Example 3:
Input:,6,2,3 [3]
Output: 8
Tip:
3 <= A.length <= 10000
1 <= A[i] <= 10^6
The analysis process
In a triangle, if the sum of any two sides is greater than the third side, or the difference between any two sides is less than the third side, it is determined that three numbers can form a triangle.
The first step
To sort the array NUMs, directly call the system sort method.
The second step
Do a for loop that iterates through the sorted array nums from end to end, so that you can start with the largest number, which is the triangle with the largest perimeter, as long as it meets the criteria.
The third step
Each time for loop:
If meet any side is greater than the sum of the third side, the triangle, as from a large number of side began to judge, so here is the biggest the perimeter of the triangle, and won’t exist before the sides of the triangle in the front, the array is sorted well, here is in the final to judge whether accord with triangle, and even meet also is not the biggest the perimeter of the triangle.
For example, [1,2,8,11], where 2 + 8 is less than 11, there will be no previous two numbers that add up to greater than 11.
If the triangle forming the maximum perimeter is found, return the sum of the three sides to end the program.
The fourth step
If the for loop ends, then any three numbers cannot form a triangle, and returns 0, ending the program.
To solve the code
Class Solution {public int largestPerimeter(int[] nums) { Sort (nums); For (int I = nums.length - 1; int I = nums.length - 1; i >= 2; -- I) {// If the sum of any two sides is greater than the third side, then the triangle is formed. Since the judgment starts from the larger side, this is the triangle with the largest perimeter. And there is no triangle with the first two sides in front, because the array has been sorted, this is to determine whether the triangle is consistent with the last, If (nums[i-1] + nums[i-2] > nums[I]) {if (nums[i-2] > nums[I]) { Return nums[i-1] + nums[i-2] + nums[I]; }} // If any three numbers do not form a triangle, return 0; }}Copy the codeSubmit the results
It took 8ms to execute, beating 99.07% of users in time, 39.1MB in memory consumption, and 27.13% in space.
The original link
The maximum perimeter of a triangle