leetcode(10)

leetcode(10)

611. Valid Triangle Number

Given an array consists of non-negative integers, your task is to count the number of triplets chosen from the array that can make triangles if we take them as side lengths of a triangle.

Example 1:

Input: [2,2,3,4]
Output: 3
Explanation:
Valid combinations are: 
2,3,4 (using the first 2)
2,3,4 (using the second 2)
2,2,3

Note:

  1. The length of the given array won’t exceed 1000.
  2. The integers in the given array are in the range of [0, 1000].

//大力出奇迹的方法,打败了1%的coder

/*class Solution {
public:
int IsTriangle(int a,int b,int c)
{
if((a+b>c)&&(a+c>b)&&(b+c>a))
return true;
else
return false;
}
int triangleNumber(vector<int>& nums) {
int size=nums.size();
int count = 0;
for(int i=0;i<size;i++)
for(int j=i+1;j<size;j++)
for(int k=j+1;k<size;k++)
{
if(IsTriangle(nums[i],nums[j],nums[k]))
count++;
}
return count;
}
};*/
class Solution {
public:
int triangleNumber(vector<int>& nums) {
vector<int> snums(nums);

//排序的好处在于只用判断a+b>c即可
sort(snums.begin(), snums.end());
int count = 0;

//大循环,最大边
for ( int n = nums.size(), k = n - 1; k > 1; --k ) {
int i = 0, j = k - 1;

//最小边和中边的循环
while ( i < j ) {

//如果满足a+b>c   那么a--b之间的所有边都满足,直接加上相应count,并让中边减1
if ( snums[i] + snums[j] > snums[k] )
count += --j - i + 1;

//如果不满足,那么将最小边右移
else
++i;
}
}
return count;
}
};




So BadJust So SoGoodCoolPretty Cool (还没人评过分呢!)
Loading...

发表评论

电子邮件地址不会被公开。 必填项已用*标注