Leetcode 611. 有效三角形的个数（DAY 182）---- 二分查找学习期

男娘i 2022-09-14 09:19 58阅读 0赞

### 文章目录 ###

*   *  原题题目
     *  代码实现（首刷天才解法^^ C++）

--------------------

## 原题题目 ##

--------------------

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATG92ZSA2_size_20_color_FFFFFF_t_70_g_se_x_16]

--------------------

## 代码实现（首刷天才解法^^ C++） ##

--------------------

**这个思路解出来发现是对的之后 也把我惊到了**  
\*\*首先`total_ret`利用了从`n`个数中选`3`个的全排列知识 因为无法利用双指针直接求能够构成三角形的数 然后就利用了先求无法构成三角形的数 减去即可得能够构成三角形的总数^^ \*\*

class Solution { 
    public:
        int triangleNumber(vector<int>& nums) { 
            if(nums.size() < 3)   return 0;
            int sub_ret = 0,total_ret = (nums.size()*(nums.size()-1)*(nums.size()-2))/6;
            sort(nums.begin(),nums.end());
            for(int i=nums.size()-1;i>=2;--i)
            { 
                int left = 0,right = i-1;
                while(left < right)
                { 
                    if(nums[left] + nums[right] > nums[i])   --right;
                    else
                    { 
                        sub_ret += (right - left);
                        ++left;
                    }
                }
            }
            return total_ret - sub_ret;
        }
    };

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATG92ZSA2_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/d05a9ce02e054ff88d44b508e5694ce4.png