题目描述
给定一个包含非负整数的数组，你的任务是统计其中可以组成三角形三条边的三元组个数。
Example 1:
输入: [2,2,3,4] 输出: 3 解释: 有效的组合是: 2,3,4 (使用第一个 2) 2,3,4 (使用第二个 2) 2,2,3
Constraints:
- 数组长度不超过1000。
- 数组里整数的范围为 [0, 1000]。
解题思路
- 排序，假设a < b < c，那么排序后的数组一定满足，b + c > a, a + c > b
- 那么只需要找到 a + b > c的即可
- 可以使用二分查找，定位最接近的那个那个k，那么k以前的都是满足条件的。
C++代码
class Solution {
public:
int triangleNumber(vector<int>& nums) {
sort(nums.begin(), nums.end());
int ans = 0;
for(int i = 0; i < nums.size(); i++){
for(int j = i + 1; j < nums.size(); j++){
int k = j;
int begin = j + 1;
int end = nums.size() - 1;
while(begin <= end){
int mid = (begin + end) / 2;
if(nums[mid] < nums[i] + nums[j]){
k = mid;
begin = mid + 1;
}else{
end = mid - 1;
}
}
ans += k - j;
}
}
return ans;
}
};
