数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++程序：计算有效三角形三元组的数量
假设我们有一个数字数组，我们需要找到从数组中选择的三个数字可以构成三角形的三元组的数量，如果我们将它们作为三角形的边长。因此，如果输入类似于 [2,2,3,4]，则结果将为 3，因为有三个三元组 [2,3,4] 使用第一个 2，[2,3,4] 使用第二个 2，以及 [2,2,3]。
为了解决这个问题，我们将遵循以下步骤：
ret := 0，n := nums 的大小，对 nums 进行排序
对于 i 在范围 n − 1 到 0 之间
right := i − 1，left := 0
当 left < right 时
sum := nums[left] + nums[right]
如果 sum > nums[i]，则将 ret 增加 right − left，将 right 减 1，否则将 left 增加 1
返回 ret
让我们看看下面的实现，以便更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int triangleNumber(vector<int>& nums) {
int ret = 0;
int n = nums.size();
sort(nums.begin(), nums.end());
for(int i = n − 1; i >= 0; i−−){
int right = i − 1;
int left = 0;
while(left < right){
int sum = nums[left] + nums[right];
if(sum > nums[i]){
ret += right − left;
right−−;
}else left++;
}
}
return ret;
}
};
main(){
vector<int> v = {2,2,3,4};
Solution ob;
cout << (ob.triangleNumber(v));
}输入
[2,2,3,4]
输出
3
更新于: 2020年10月21日
736 次浏览
广告