611. 有效三角形的個數(shù)

給定一個包含非負(fù)整數(shù)的數(shù)組，你的任務(wù)是統(tǒng)計其中可以組成三角形三條邊的三元組個數(shù)。

示例 1:

輸入: [2,2,3,4] 輸出: 3 解釋: 有效的組合是: 2,3,4 (使用第一個 2) 2,3,4 (使用第二個 2) 2,2,3

注意:

• 數(shù)組長度不超過1000。
• 數(shù)組里整數(shù)的范圍為 [0, 1000]。

解題思路

先將數(shù)組從小到大進(jìn)行排序，固定一條邊i，遍歷另一條邊j，我們發(fā)現(xiàn)當(dāng)j在不斷增大的時候，我們的第三邊也可以繼續(xù)在原來的基礎(chǔ)上加大，因此我們只需要維護(hù)第三邊的指針k

代碼

class Solution {public int triangleNumber(int[] nums) {Arrays.sort(nums);int n=nums.length,res=0;for(int i=0;i<n;i++){int k=i;for (int j=i+1;j<n;j++){while (k+1<n&&nums[k+1]<nums[i]+nums[j])k++;res+= Math.max(0,k-j);}}return res;} }

總結(jié)

以上是生活随笔為你收集整理的611. 有效三角形的个数的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。