题解 | #合法的三角形个数#
合法的三角形个数
http://www.nowcoder.com/practice/e6ee5545535445feaeb92f357644fb14
该题的解法如下：
首先，对各边长进行排序，方便获取三边中最长的边。
然后，进入循环，循环体如下：
由小到大找最长边（循环）
从最长边开始由大到小找次长边（循环）
从次长边开始由大到小找最短边。(循环计数法，或者用二分查找法找上界，然后用计算中间个数）
//循环计数法
int validTriangleNumber1(vector<int>& nums)
{
int length = nums.size();
if (length < 3) return 0;
sort(nums.begin(), nums.end());//排序
int res = 0;
for (int right = 2; right < length; ++right)//right最长边序号
{
for (int mid = right - 1; mid > 0; --mid)//mid次长边序号
{
int temp = nums[right] - nums[mid];//找出最短边的最短长度temp
if (temp > nums[mid]) break;//如果最短边长度的最短长度已经比次长长，打断循环
for (int left = mid - 1; left >=0 ; --left) //left最短边序号
{
if (nums[left] <= temp)
break;
++res;//计数
}
}
}
return res;
}
//二分查找上界法
int validTriangleNumber(vector<int>& nums)
{
int length = nums.size();
if (length < 3) return 0;
sort(nums.begin(), nums.end());//排序
int res = 0;
for (int right = 2; right < length; ++right)//right最长边序号
{
for (int mid = right - 1; mid > 0; --mid)//mid次长边序号
{
int temp = nums[right] - nums[mid];//找出最短边的最短长度temp
if (temp > nums[mid]) break;//如果最短边长度的最短长度已经比次长长，打断循环
auto bg = nums.begin();
auto upperBound = upper_bound(bg, bg + mid, temp);//利用二分法找出最短边长度上界
res += mid - (upperBound - bg);//计算中间边的个数
}
}
return res;
}
