题目描述

题目链接：611.有效三角形的个数

算法原理

解法一：暴力求解(超时）

三层for循环枚举出所有的三元组，并且判断是否能构成三⻆形。
虽然说是暴⼒求解，但是还是想优化⼀下：
判断三⻆形的优化：

• 如果能构成三⻆形，需要满⾜任意两边之和要⼤于第三边。但是实际上只需让较⼩的两条边之和⼤于第三边即可。
• 因此我们可以先将原数组排序，然后从⼩到⼤枚举三元组，⼀⽅⾯省去枚举的数量，另⼀⽅⾯⽅便判断是否能构成三⻆形。

解法二：排序＋双指针

先将数组排序。
根据解法⼀中的优化思想，我们可以固定⼀个最⻓边，然后在⽐这条边⼩的有序数组中找出⼀个⼆元组，使这个⼆元组之和⼤于这个最⻓边。由于数组是有的，我们可以利⽤对撞指针来优化。
设最⻓边枚举到i 位置，区间[left, right] 是i 位置左边的区间（也就是⽐它⼩的区间）：
如果nums[left] + nums[right] > nums[i] ：

• 说明[left, right - 1] 区间上的所有元素均可以与nums[right] 构成⽐nums[i] ⼤的⼆元组
• 满⾜条件的有right - left 种

此时right 位置的元素的所有情况相当于全部考虑完毕， right-- ，进⼊下⼀轮判断。如果nums[left] +nums[right] <= nums[i]：

• 说明left 位置的元素是不可能与[left + 1, right] 位置上的元素构成满⾜条件的⼆元组
• left 位置的元素可以舍去， left++ 进⼊下轮循环

代码实现

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        //1.排序
        sort(nums.begin(),nums.end());

        //2.利用双指针解决问题
        int ret = 0,n = nums.size();
        for(int i = n - 1;i >= 2;--i)//先固定最大的数
        {
            //利用双指针快速统计符合要求的三元组的个数
            int left = 0,right = i - 1;
            while(left < right)
            {
                if(nums[left] + nums[right] > nums[i])
                {
                    ret += right - left;
                    --right;
                }
                else
                {
                    left++;
                }
            }
        }
        return ret;
    }
};