模块一——双指针：611.有效三角形的个数

题目描述

题目链接：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;
    }
};