1.指针对撞问题（利用有序数组的单调性衍生）

1.1LCR 179. 查找总价格为目标值的两个商品 - 力扣（LeetCode）​​​​​​

1.1.1题目解析

有序数组，找到和为price的两个元素，只需要一个解即可。

1.1.2算法原理

a.解法一：两层for循环暴力枚举，时间复杂度O()；空间复杂度O(1);

b:解法二：利用双指针对撞，left指向最左边元素，right指向最右边元素，利用单调性原理，如果他们的和大于price，那么left++，如果和小于price，那么right--，等于price直接return。时间复杂度O（N），空间复杂度O（1）

1.1.3代码实现

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){left++;}else return{price[left],price[right]};}return{-1,-1};}
};

1.2611. 有效三角形的个数 - 力扣（LeetCode）

1.2.1题目解析：

给定一个数组nums，找出可以组成三角形三条边的三元组个数

1.2.2算法解析：

a.解法一：三层for循环，暴力枚举，时间复杂度O（N^3），空间复杂度O（1）；

b.解法二：两小边之和大于第三边时就能确定三角形成立。因此我们可以先将数组排序，这样较大的数就在右边，较小的数就在左边。我们可以先固定一个三角形中最大边maxn，那么较小的两条边就在大边的左边寻找。定义left为最左边元素，right为最右边元素。  

如果left+right>maxn时，那么证明此时为三角形，同时因为left左边的数都比left大，那么left依次变为left左边时都可以成立，那么就可以计入right-left个三角形。之后right--，继续去寻找；

如果left+right<=maxn时。那么left就要++，去寻找更大的数。

当left==right时就停止，接下来就改变固定的大数，继续寻找。时间复杂度O(N*longN)+O(N^2),空间复杂度O（1）；例[2,2,3,4]

1.2.3代码解析：

class Solution {
public:int triangleNumber(vector<int>& nums) {sort(nums.begin(),nums.end());int maxn = nums.size()-1;int ret = 0;while(maxn >= 2){int left = 0,right = maxn-1;while(right > left){if(nums[left] + nums[right] > nums[maxn]){ret+= right - left;right--;}else{left++;}}maxn--;}return ret;}
};