【LeetCode刷题】有效三角形个数、查找总价值为目标值的两个商品

本文主要是介绍【LeetCode刷题】有效三角形个数、查找总价值为目标值的两个商品，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【LeetCode刷题】Day 5

题目1：611.有效三角形个数
- 思路分析：
- 思路1：暴力枚举O(N^3^)
- 思路2：单调性，双指针解法O(NlogN+N^2^)
题目2：LCR 179.查找总价格为目标值的两个商品
- 思路1：暴力枚举O(N^2^)
- 思路2：单调性，双指针O(N)
今日收获：

在这里插入图片描述

题目1：611.有效三角形个数

在这里插入图片描述

思路分析：

判断三边能形成三角形的条件：

任意两边之和大于第三边。a+b>c && a+c>b && b+c>a;
已知：a<= b <= c，只需要a+b>c即可。因为c最大，加上任意一个数肯定大于第三个。

思路1：暴力枚举O(N³)

三层循环，一层确定一个数，然后再判断，即可。

思路2：单调性，双指针解法O(NlogN+N²)

在这里插入图片描述
举例说明：如上图[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++;} elseright--;}}return count;}
};

LeetCode链接：611.有效三角形个数

题目2：LCR 179.查找总价格为目标值的两个商品

在这里插入图片描述

思路1：暴力枚举O(N²)

思路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]};elseleft++;}return {};}
};