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

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

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

class Solution {
public:
    int triangleNumber(vector& 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;
    }
};