在做题中学习（40）：有效三角形的个数

611. 有效三角形的个数 - 力扣（LeetCode）

思路：（双指针法）最优

确定一个三角形除了左边，

还可以右边的让数组排好序，让一个小的，一个次大 相加 和 最大的 比较，如果不满足，中间的数都可以直接不用比较，如果满足，那 次大 和 中间的数 全部都可以组成，直接计数就行。而这就分为了两种情况：

1.a+b>c? ? ? ? (right--)

2.a+b<=c? ? ? (left++)

两者相遇后，把最大数c--，再次重复上面操作。

class Solution 
{
public:
    int triangleNumber(vector<int>& nums) 
    {
        int count = 0;
        //1.先排序
        sort(nums.begin(),nums.end());
        //2.确定c
        for(int i=nums.size()-1;i>=2;i--)
        {
            //在里面定义left和right是因为每次变，它们就得跟着变
            int left = 0, c = i, right = i-1;
            while(left<right)
            {

                if(nums[left]+nums[right]>nums[c])
                {
                    count += right-left;
                    right--;
                }
                else
                {
                    left++;
                }

            }
        }
        
        return count;
    }
};