1.題目解析

給定一個包含非負整數的數組?nums?，返回其中可以組成三角形三條邊的三元組個數。

補充：

1.三角形的判斷：假設有三條邊按大小排序：

?2.題目示例

示例 1:

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

示例 2:

輸入: nums = [4,2,3,4]
輸出: 4

?分析題目可知是要算上重復的

3.算法分析：

①暴力枚舉：

時間復雜度較高O(3*n^3)

三層for循環確定三條邊，再定義一個計數器計算有小三角形的個數

//暴力枚舉public int triangleNumber(int[] nums) {Arrays.sort(nums);int count=0;int len=nums.length;for(int i=0;i<len;i++){for(int j=i+1;j<len;j++){for(int k=j+1;k<len;k++){if(nums[i]+nums[j]>nums[k]){count++;}}}}return count;}

集美們，不用跑了，我幫你們試過了，過不了

解法二：

利用單調性和雙指針的方法：

舉個例子：

2，2，3，4，5，6，7，8，9，10

1.設置一個最大值

2.在最大數的左區間內，使用雙指針和單調性的方法計算出有效三角形的個數

本寶寶建議你自己畫一畫，真正理解這個算法。

?會出現兩種情況：

①left+right>max? ? ? ? ? ?count+=right-left right--

②left+right=<max? ? ? ? ?lrft++

?代碼實現：

 public int triangleNumber(int[] nums) {int len=nums.length;int count=0;for(int i=len-1;i>=0;i--){int max=nums[i];int left=0;int right=i-1;while (left<right){if(nums[left]+nums[right]>max){count+=right-left;right--;}else{left++;}}}return  count;}

當然這個代碼你是跑不過的，為什么呢？

因為你無法確定最大值，我舉的栗子正好是我排過序的，若是沒有排過序，不僅找不到最大值，還無用大學生的方法判斷是否是有效三角形，所以一定要先排序(這都是姐走過的彎路)

 public int triangleNumber(int[] nums) {Arrays.sort(nums);int len=nums.length;int count=0;for(int i=len-1;i>=0;i--){int max=nums[i];int left=0;int right=i-1;while (left<right){if(nums[left]+nums[right]>max){count+=right-left;right--;}else{left++;}}}return  count;}

?本題完，歡迎指正