题目1：611.有效三角形个数
思路分析：
判断三边能形成三角形的条件：
- 任意两边之和大于第三边。a+b>c && a+c>b && b+c>a;
- 已知：a<= b <= c，只需要a+b>c即可。因为c最大，加上任意一个数肯定大于第三个。
思路1：暴力枚举O(N3)
三层循环，一层确定一个数，然后再判断，即可。
思路2：单调性，双指针解法O(NlogN+N2)
举例说明：如上图[2,2,3,4,5,9,10]，先固定10，再两个指针分别指向第二大数9和最小数2，2+9>10，增加2，肯定也成立，则2到5都成立。反之，则移动左指针，指向更大的数，寻找是否有成立的数。直到左右指针相同，则与10有关的结束，在统计与9有关且不与10有关的组合。
代码实现：
注意：此处代码采取的是逆序，与上面分析相反。
class Solution { public: int triangleNumber(vector<int>& nums) { if (nums.size() < 3) return 0; sort(nums.begin(), nums.end(), greater()); int count = 0; for (size_t i = 0; i < nums.size() - 2; i++) { int left = i + 1, right = nums.size() - 1; while (left != right) { if (nums[right] + nums[left] > nums[i]) { count += right - left; left++; } else right--; } } return count; } };
题目2：LCR 179.查找总价格为目标值的两个商品
思路1：暴力枚举O(N2)
思路2：单调性，双指针O(N)
这里的数组都是有序的，所以最大值加最小值所得的sum，如果sum大于target，则减小最大值；
反之，增加最小值；直到找到相等；
代码实现：
class Solution { public: vector<int> twoSum(vector<int>& price, int target) { int left = 0, right = price.size() - 1; while (left < right) { if (price[left] + price[right] > target) right--; else if (price[left] + price[right] == target) return {price[left], price[right]}; else left++; } return {}; } };
LeetCode链接：LCR 179.查找总价格为目标值的两个商品
今日收获：
- 双指针和单调性的结合；
- 返回是vector时，可以返回{}；
