目錄
1.題目鏈接：611.有效三角形的個數
2.題目描述：
3.解法一：(暴力解法)(會超時)：
4.解法二(排序+雙指針)
1.題目鏈接：611.有效三角形的個數
2.題目描述：
?
給定一個包含非負整數的數組?nums?，返回其中可以組成三角形三條邊的三元組個數。
示例 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.解法一：(暴力解法)(會超時)：
算法思路：
三層for循環枚舉出所有的三元組，并且判斷是否能構成三角形。雖然說是暴力求解，但是還是可以優化一下：
判斷三角形的優化
- 如果能構成三角形，需要滿足任意兩邊之和大于第三邊。但是實際上只需讓較小的兩條邊之和大于第三邊既可。
- 因此我們可以先將原數組排序，然后從小到大枚舉三元組，一方面省去枚舉的數量，另一方面方便判斷是否能構成三角形。
class Solution
{
public:int triangleNumber(vector<int>& nums){//1.排序sort(nums.begin(), nums.end());int n = nums.size(), ret = 0;//2.從小到大枚舉所有的三元組for (int i = 0; i < n; i++){for (int j = i + 1; j < n; j++){for (int k = j + 1; k < n; k++){ //當最小的兩個邊之和大于第三個邊的時候，統計答案if (nums[i] + nums[i] > nums[k])ret++;}}}return ret;}
};4.解法二(排序+雙指針)
算法思路：
先將數組排序。
根據解法一中的優化思想，我們可以固定一個最長邊，然后在比這條邊小的有序數組中找出一個二元組，使這個二元組之和大于這個最長邊。由于數組使有序的，我們可以利用對撞指針來優化。
設最長邊枚舉到i位置，區間[left,right]是i位置左邊的區間（也就是比他小的區間）：
- 如果nums[left] + nums[right] > nums[i]:
說明[left,right-1]區間上的所有元素均可以與nums[right]構成比nums[i]大的二元組? ? ? ? ? ? 滿足條件的有right - left種? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 此時right位置的元素的所有情況相當于全部考慮完畢，right--，進入下一輪判斷- 如果nums[left] + nums[right] <= nums[i]:
說明left位置的元素是不可能與[left+1,right]位置上的元素構成滿足條件的二元組? ? ? ? ? ? ? ?left位置的元素可以舍去，left++進入下輪循環
class Solution {
public:int triangleNumber(vector<int>& nums) {int sum = 0,n = nums.size();sort(nums.begin(),nums.end());for(int i = n - 1;i>=2;i--){int left = 0,right = i-1;while(left<right){if(nums[left] + nums[right] > nums[i]){sum += (right - left);right--;}else{left++;}}}return sum;}
};
