目录
1.有效三角形个数
给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。
示例 1:
输入: nums = [2,2,3,4] 输出: 3 解释:有效的组合是: 2,3,4 (使用第一个 2) 2,3,4 (使用第二个 2) 2,2,3
示例 2:
输入: nums = [4,2,3,4] 输出: 4
1.1 题目分析
针对于这个题目，我们可以基于排序和对撞指针来解决。对于组成三角形的三条边，硬性要求 a+ b > c，所以所有 a + b < c 的组合我们都不需要看。
1.2 解法
基于排序和对撞指针的做法：
a）先对数组进行排序，固定一个 ”最长边“，然后在比这条边小的有序数组中找出一个二元组，使这个二元组之和大于这个最长边。
b）设 int i = nums.length-1 ，left = 0，right = i-1；
c）如果 num[left] + nums[right] > nums[i]
则说明有在 [left,right] 这个区间内随机找出两个数也不可能比 nums[i] 大，所以 right-left 这个区间内都是符合三角形特征的，就有 right-left 种情况。随后 i -- ，进行下一个区间的检测。
d）如果 num[left] + nums[right] < nums[i]
让 left++，循环条件为 left<right，让[ left, right ] 这个区间内的和尽可能增大。
e）当 d 过程进行完毕时，这说明这个区间内没有符合三角形特征的了。更换固定的 "最长边" ，把 i--，从 b 开始进行新一轮循环。
1.2 代码实现
class Solution {
public int triangleNumber(int[] nums) {
int count =0, n = nums.length-1;
for(int i= n;i>=2;i--){
int right = i-1;
int left = 0;
while(left<right){
if(nums[right] + nums[left] > nums[i]){
count += right-left;
right--;
}else{
left++;
}
}
}
return count;
}
}2. 和为 S 的两个数字
LCR 179. 查找总价格为目标值的两个商品 - 力扣（LeetCode）
购物车内的商品价格按照升序记录于数组 price。请在购物车中找到两个商品的价格总和刚好是 target。若存在多种情况，返回任一结果即可。
示例 1：
输入：price = [3, 9, 12, 15], target = 18 输出：[3,15] 或者 [15,3]
示例 2：
输入：price = [8, 21, 27, 34, 52, 66], target = 61 输出：[27,34] 或者 [34,27]
2.1 题目分析
注意题目给出的数组有序特性，使用对撞指针解决问题。
2.2 解法
a）初始化 left，right 分别指向数组的左右两端
b）当 left<right 时一直循环
i）当 nums[left] + nums[right] == target 时，记录结果并返回。
ii）当 nums[left] + nums[right] < targer 时，因为整个数组是升序的，所以可以舍去最小值，来让 nums 之和增大，直到 nums 之和与 target 相等。
iii）当 nums[left] + nums[right] > target 时，因为整个数组是升序的，所以可以舍去最大值，来让 nums 之和减小，直到 nums 之和与 targer 相等。
2.3 代码实现
class Solution {
public int[] twoSum(int[] price, int target) {
int left =0, right = price.length-1;
while(left<right){
int sum = price[left] + price[right];
if(sum == target){
return new int[] {price[left],price[right]};
}
if(sum < target){
left++;
}
if(sum > target){
right --;
}
}
return new int[] {0,-1};
}
}