每日一题系列（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循环改为二分查，并不是很容易想得到。第三种双指针是更难想了，本质上是将一个值固定不变，让两个指针分别代表三角形的两条边与这个固定值比较，比较是否构成三角形，再利用单调性的性质，将时间复杂度大大缩短。
