算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !
今天和大家聊的问题叫做 有效三角形的个数,我们先来看题面:
https://leetcode.cn/problems/valid-triangle-number/
Given an integer array nums, return the number of triplets chosen from the array that can make triangles if we take them as side lengths of a triangle.
给定一个包含非负整数的数组 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
解题
排序+二分查找
class Solution {
public:
int triangleNumber(vector<int>& nums) {
int res = 0;
int n = nums.size();
//先进行排序 为二分查找建立条件
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];
//二分查找第三条符合得边 发现了二分查找的一个边界问题 right能否被取到是关键是<= 还是<
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 ;
}
}
//判断边界 如果右边界都满足那么左边界到右边界上的每一个元素都满足
if(nums[right]<sum){
res = res + right - j;
}
}
}
return res;
}
};
上期推文: