每日一题：LeetCode-611. 有效三角形的个数

每日一题系列（day 14）

前言：

🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈

?? 🔎🔎如果说代码有灵魂，那么它的灵魂一定是👉👉算法👈👈，因此，想要写出💚优美的程序💚，核心算法是必不可少的，少年，你渴望力量吗😆😆，想掌握程序的灵魂吗???那么就必须踏上这样一条漫长的道路🏇🏇，我们要做的，就是斩妖除魔💥💥，打怪升级！💪💪当然切记不可😈走火入魔😈，每日打怪，拾取经验，终能成圣🙏🙏！开启我们今天的斩妖之旅吧！????

---

题目：

??给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。

示例：

提示：

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 1000

思路：

??根据题意，求满足称为三角形的三元组的对数，数组内有重复值也算，最简单的方法就是用暴力，三层for循环枚举出所有情况，第一层for控制i指向第一个数，第二层for循环控制j指向i的下一个位置，最后一层for循环k指向j的下一个元素，每层for循环都要保证小于数组的大小防止越界，最后根据两边之和大于第三边，随意将两个指针相加与第三个指针进行比较，如果大于计数+1，最后枚举出全部三元组。

代码实现：

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        int len = nums.size();
        int cnt = 0;
        for(int i = 0 ; i < len ; i++)
        {
            for(int j = i + 1; j < len ; j++)
            {
                for(int k = j + 1; k < len ; k++)
                {
                    if(nums[i] + nums[j] > nums[k])
                    {
                        cnt ++;
                    }
                }
            }
        }
        return cnt;
    }
};

??测试用例可以过，但是提交却过不了，这说明我们三层for循环时间复杂度 O(n^3) 还是太高了，我们可以想办法优化一下，三层for循环时间复杂度过高，那还有什么方法能够再优化一下呢？

??我们可以只使用两层for循环，这两层for循环和上面一样只是为了索引三角形的两条边，我们索引第三条边可以使用二分查找来查找第三个值，但是二分查找使用的前提是数组有序，所以在我们遍历数组之前，一定还要将数组进行排序，这样才能使用二分查找。
??同时，我们不能确定数组里面的元素是否全为0，这样也是不能构成三角形的，或者数组里面的前N位是0，后面又不是0这种，所以我们在开始操作之前，使用循环将i的指向的位置为非0位置。

代码实现：

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        int len = nums.size();
        if(len < 3) return 0;
        sort(nums.begin(), nums.end());

        int i = 0;
        while(!nums[i]) i++;
        
        int ret = 0;
        for(; i < len ; i++)
        {
            for(int j = i + 1 ; j < len ; j++)
            {
                int left = j, right = len;
                int mid = 0;
                while(left < right)
                {
                    mid = (right + left)/2;
                    if(nums[mid] < nums[i] + nums[j])  left = mid + 1;
                    else right = mid;
                } 
                ret += (left - j - 1);
            }
        }
        return ret;
    }
};

??我们就可以通过了，这样时间复杂度就降低到 O(logn * n^2) 了，但是我们发现这样时间复杂度还是有些高了。其实还有一种双指针解法更加高效巧妙且灵活。

---

思路：

??使用双指针解法，首先将数组排序，将最大元素设为比较元素，即最后一个元素是比较元素，设置left指针指向数组的0位置处，right指针指向比较元素前一个位置，这就是初始状态了。



??这时左指针与右指针指向的值相加与比较值进行比较，我们发现，nums[left]+nums[right]>nums[nums.size() - 1]的，然而数组又是有序数组，既然0位置处与右指针的值相加要大于比较值，那么在[left,right]这段区间内，左指针向右指针靠拢时，左右指针的和一定是要大于比较值的，所以符合题意的三元组就是right-left组了，我们可以在外部设置ret变量来接收这个值。
??9这个位置的值已经枚举完了，那么我们将right指针向左走一步，重复上述步骤，但是如果当nums[left]+nums[right]<nums[nums.size()-1]时，我们就要移动左指针了，如果当两指针相遇时还没有大于比较值的数，那么左边的情况也不需要再枚举了，因为递增数组1，最大的两个数相加都没有大于比较值，更何况比他们要小的值，所以当两指针相遇时，以当前比较值为基准的情况已经全部枚举完成。
??那么这个比较值就要向前移动一位，然后再重复上述步骤，直到比较值将nums[2]这个位置的值枚举完（因为三角形最低要三条边），整个数组符合条件的三元组就被我们记录下来了。

代码实现：

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end());//保证数组有序
        int ret = 0;
        int n = nums.size() - 1;
        for(int i = n ; i >= 2 ; i--)//这层for循环表示比较值的位置
        {
            int left = 0, right = i - 1;
            while(left < right)
            {
                if(nums[left] + nums[right] > nums[i])
                {
                    ret += right - left;
                    right--;
                }
                else
                {
                    left++;
                }
            }
        }
        return ret;//返回三元组的个数
    }
};

---

??三种解题方式，暴力方法最为直接，也最容易想得到，在此基础上将暴力优化，第三层for循环改为二分查，并不是很容易想得到。第三种双指针是更难想了，本质上是将一个值固定不变，让两个指针分别代表三角形的两条边与这个固定值比较，比较是否构成三角形，再利用单调性的性质，将时间复杂度大大缩短。