一、題目
給定一個(gè)包含非負(fù)整數(shù)的數(shù)組?nums?，返回其中可以組成三角形三條邊的三元組個(gè)數(shù)。
示例 1:
輸入: nums = [2,2,3,4] 輸出: 3 解釋:有效的組合是: 2,3,4 (使用第一個(gè) 2) 2,3,4 (使用第二個(gè) 2) 2,2,3
示例 2:
輸入: nums = [4,2,3,4] 輸出: 4
二、思路解析
這道題，有一點(diǎn)挺新鮮的：構(gòu)成三角形的三條邊，僅需滿足 2 條最短邊之和大于等于第三條邊即可。
以前的羅根，就總是傻傻地求 3 次??
今天這道題，算是又打開了我新世界的大門，也提醒著我要虛心求學(xué)，切勿狂妄自大。
咳咳，閑話嘮完了，我們回到這道題來??
知道了上面這個(gè)定理，我們就可以先給數(shù)組排個(gè)序，再利用 雙指針 進(jìn)行解答，具體步驟我也有在下面代碼注釋中寫到啦。文章來源：http://www.zghlxwxcb.cn/news/detail-808463.html
三、完整代碼
class Solution {
public int triangleNumber(int[] nums) {
//1、排序
Arrays.sort(nums);
//2、利用雙指針解答
int sum = 0;
for(int i =nums.length-1;i >=2; i--){
//利用雙指針快速統(tǒng)計(jì)出符合要求的三元組的個(gè)數(shù)
int left = 0;
int right =i-1;
//算法實(shí)現(xiàn)部分
while(left < right){
if(nums[left] + nums[right] > nums[i]){
sum += right - left;
right--;
}else{
left++;
}
}
}
return sum;
}
}以上就是本篇博客的全部?jī)?nèi)容啦，如有不足之處，還請(qǐng)各位指出，期待能和各位一起進(jìn)步！文章來源地址http://www.zghlxwxcb.cn/news/detail-808463.html
到了這里，關(guān)于「優(yōu)選算法刷題」:有效三角形的個(gè)數(shù)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
