科泉网站,《网站建设》期末考试,节省时间用wordpress,网页中的基本元素有哪些优质专栏#xff1a;算法_云边有个稻草人的博客-CSDN博客
目录
【611. 有效三角形的个数 - 力扣#xff08;LeetCode#xff09;】 解法一#xff1a; 解法二#xff1a; 【611. 有效三角形的个数 - 力扣#xff08;LeetCode#xff09;】 解法一#xff1a; 三层for…优质专栏算法_云边有个稻草人的博客-CSDN博客
目录
【611. 有效三角形的个数 - 力扣LeetCode】 解法一 解法二 【611. 有效三角形的个数 - 力扣LeetCode】 解法一 三层for循环枚举出所有三元组判读每组是否能构成三角形会超时但是我们可以再优化一下先对数组进行排序只需判断三元组中最小的两个数是否大于第三个数即可省略有一些不必要的判断。 class Solution {
public:int triangleNumber(vectorint 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[j] nums[k])ret;}}}return ret;}
}; 解法二 时间复杂度为O(N)。 class Solution
{
public:int triangleNumber(vectorint nums) {//1.先对数组进行排序sort(nums.begin(),nums.end());//2.利用双指针解决问题int ret 0,n nums.size();for(int i n-1;i2;i--)//固定最大的那个数{int left 0,right i-1;while(left right){if((nums[left]nums[right])nums[i]){ret right-left;right--;}elseleft;}}return ret;}
}; 完—— 明天继续。。。
