資料結構
網路
關係型資料庫管理系統
作業系統
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 次瀏覽
廣告