有效三角形的个数
Category Difficulty Likes Dislikes
algorithms Medium (53.27%) 447 -
Tags
Companies
给定一个包含非负整数的数组 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
提示:
1 <= nums.length <= 1000
0 <= nums[i] <= 1000
Discussion | Solution
// 这是一个排序+二分的解法， 排序+双指针解法会更优，减少了二分查找的时间，三个点的活动窗口，固定一个滑动其他两个
class Solution {
public:
int triangleNumber(vector<int>& nums) {
int ans = 0;
sort(nums.begin(), nums.end());
int target = 0, temp = 0;
for(int i=0;i<nums.size();i++)
{
for(int j=i+1;j<nums.size();j++)
{
target = nums[i] + nums[j];
temp = findPoint(nums,j+1,nums.size(),target);
ans += temp-j-1;
}
}
return ans;
}
int findPoint(vector<int>& nums, int l, int r, int target)
{
while(l < r)
{
int mid = l + ((r-l)>>1);
if(nums[mid] < target)
l = mid + 1;
else
r = mid;
}
return l;
}
};