題目：
給定一個(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
提示:
1 <= nums.length <= 10000 <= nums[i] <= 1000
算法原理：
三角形構(gòu)成條件：任意兩邊之和一定要大于第三邊
其實(shí)在判斷中，只需要判斷最小的兩邊和大于最長(zhǎng)的一邊即可
假設(shè) a<=b<=c
若要構(gòu)成三角形，a+b>c? a+c>b b+c>a
其實(shí)a+c>b b+c>a是顯然的，只需要判斷a+b>c即可
1 排序（升序）
2 依次固定一個(gè)最大數(shù)c
? ? 從c左邊的區(qū)間中選擇a，b，滿足a+b>c
? ? 左邊界left，右邊界right
? ? a 若是nums[left]+nums[right]>C
? ? ? ?則nums[right]與區(qū)間內(nèi)的任意一個(gè)（包括左邊界）組合都能>C，個(gè)數(shù)是right-left
? ? ? ?那么右邊界的所有組合都統(tǒng)計(jì)完畢，right--
? ? b 若是nums[left]+nums[right]<=C
? ? ? ?當(dāng)nums[left]+nums[right]<C，那么nums[left]與區(qū)間內(nèi)的任意一個(gè)組合都<C, left++文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-674845.html
? ? ? ?當(dāng)nums[left]+nums[right]=C，那么left++，舍棄較小的數(shù)文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-674845.html
代碼實(shí)現(xiàn)：
class Solution
{
public:
int triangleNumber(vector<int>& nums)
{
int n = nums.size();
sort(nums.begin(),nums.end());
int count = 0;
for(size_t i = n-1;i>=2;i--)//依次固定最大數(shù)C
{
int left = 0;
int right = i-1;
while(left<right)
{
if(nums[left]+nums[right]>nums[i])//a+b>c
{
count+=right-left;
right--;
}
else //a+b<=c
{
left++;
}
}
}
return count;
}
};到了這里，關(guān)于雙指針?biāo)惴▽?shí)例5（有效三角形的個(gè)數(shù)）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
