611. 有效三角形的個數

給定一個包含非負整數的數組，你的任務是統計其中可以組成三角形三條邊的三元組個數。

示例 1:

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

注意:

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

解題思路

先將數組從小到大進行排序，固定一條邊i，遍歷另一條邊j，我們發現當j在不斷增大的時候，我們的第三邊也可以繼續在原來的基礎上加大，因此我們只需要維護第三邊的指針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;}
}