?LeetCode刷題實(shí)戰(zhàn)611：有效三角形的個(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

class?Solution?{
public:
????int?triangleNumber(vector<int>& nums)?{
????????int?res = 0;
????????int?n = nums.size();
????????//先進(jìn)行排序 為二分查找建立條件
????????sort(nums.begin(),nums.end());
????????for(int?i = 0; i < n - 2; ++i){
????????????for(int?j = i + 1; j < n - 1; ++j){
????????????????//固定兩條邊
????????????????int?sum = nums[i]+nums[j];
????????????????//二分查找第三條符合得邊 發(fā)現(xiàn)了二分查找的一個(gè)邊界問題 right能否被取到是關(guān)鍵是<= 還是<
????????????????int?left = j + 1;
????????????????int?right = n - 1;
????????????????while(left <= right){
????????????????????int?mid = (right-left)/2?+ left;
????????????????????if(nums[mid] < sum){
????????????????????????left = mid + 1;
????????????????????}else{
????????????????????????right = mid - 1?;
????????????????????}
????????????????}
????????????????//判斷邊界 如果右邊界都滿足那么左邊界到右邊界上的每一個(gè)元素都滿足
????????????????if(nums[right]????????????????????res = res + right - j;
????????????????}
????????????}
????????}
????????return?res;
????}
??
};