【优选算法】（第三篇）
目录
有效三⻆形的个数（medium）
题目解析
讲解算法原理
编写代码
和为s的两个数字（easy）
题目解析
讲解算法原理
编写代码
有效三⻆形的个数（medium）
题目解析
1.题目链接：. - 力扣（LeetCode）
2.题目描述
给定⼀个包含⾮负整数的数组 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
解释：
4,2,3
4,2,4
4,3,4
2,3,4
讲解算法原理
解法⼀（暴⼒求解）（会超时）：算法思路：
三层 for 循环枚举出所有的三元组，并且判断是否能构成三⻆形。虽然说是暴⼒求解，但是还是想优化⼀下：
判断三⻆形的优化：
▪ 如果能构成三⻆形，需要满⾜任意两边之和要⼤于第三边。但是实际上只需让较⼩的两条边
之和⼤于第三边即可。
▪ 因此我们可以先将原数组排序，然后从⼩到⼤枚举三元组，⼀⽅⾯省去枚举的数量，另⼀⽅
⾯⽅便判断是否能构成三⻆形。
算法代码：
class Solution {
public:
int triangleNumber(vector<int>& nums) {
// 1. 排序
sort(nums.begin(), nums.end());
int n = nums.size(), ret = 0;
// 2. 从⼩到⼤枚举所有的三元组
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
for (int k = j + 1; k < n; k++) {
// 当最⼩的两个边之和⼤于第三边的时候，统计答案
if (nums[i] + nums[j] > nums[k])
ret++;
}
}
}
return ret;
}
};解法⼆（排序+双指针）：
算法思路：
先将数组排序。
根据「解法⼀」中的优化思想，我们可以固定⼀个「最⻓边」，然后在⽐这条边⼩的有序数组中找出⼀个⼆元组，使这个⼆元组之和⼤于这个最⻓边。由于数组是有序的，我们可以利⽤「对撞指
针」来优化。
设最⻓边枚举到 i 位置，区间 [left, right] 是 i 位置左边的区间（也就是⽐它⼩的区间）：
◦ 如果 nums[left] + nums[right] > nums[i] ：
▪ 说明 [left, right - 1] 区间上的所有元素均可以与 nums[right] 构成⽐
nums[i] ⼤的⼆元组
▪ 满⾜条件的有 right - left 种
▪ 此时 right 位置的元素的所有情况相当于全部考虑完毕， right-- ，进⼊下⼀轮判断◦ 如果 nums[left] + nums[right] <= nums[i] ：
▪ 说明 left 位置的元素是不可能与 [left + 1, right] 位置上的元素构成满⾜条件
的⼆元组
▪ left 位置的元素可以舍去， left++ 进⼊下轮循环
如图所示：
只需要排序后将最大值设为叔祖最后面，再利用双指针解法，相比较left和right来说有以上两种操作，在进行对应的操作，只需要遍历一遍数组，此时的时间复杂度是非常可观的
编写代码
c++算法代码：
class Solution
{
public:
int triangleNumber(vector<int>& nums)
{
// 1. 优化
sort(nums.begin(), nums.end());
// 2. 利⽤双指针解决问题
int ret = 0, n = nums.size();
for(int i = n - 1; i >= 2; i--) // 先固定最⼤的数 {
// 利⽤双指针快速统计符合要求的三元组的个数 int left = 0, right = i - 1;
while(left < right)
{
if(nums[left] + nums[right] > nums[i])
{
ret += right - left;
right--;
}
else
{
left++;
}
}
}
return ret;
}
};java算法代码：
class Solution
{
public int triangleNumber(int[] nums)
{
// 1. 优化：排序
Arrays.sort(nums);
// 2. 利⽤双指针解决问题
int ret = 0, n = nums.length;
for(int i = n - 1; i >= 2; i--) // 先固定最⼤的数
{
// 利⽤双指针快速统计出符合要求的三元组的个数
int left = 0, right = i - 1;
while(left < right)
{
if(nums[left] + nums[right] > nums[i])
{
ret += right - left;
right--;
}
else
{
left++;
}
}
}
return ret;
}
}
和为s的两个数字（easy）
题目解析
1.题目链接：. - 力扣（LeetCode）
2.题目描述
输⼊⼀个递增排序的数组和⼀个数字 s ，在数组中查找两个数，使得它们的和正好是 s 。如果有多对数字的和等于 s ，则输出任意⼀对即可。
⽰例1：
输⼊： nums = [2,7,11,15], target = 9
输出： [2,7] 或者 [7,2]
讲解算法原理
解法⼀（暴⼒解法，会超时）：
算法思路：
两层 for 循环列出所有两个数字的组合，判断是否等于⽬标值。
算法流程：
两层 for 循环：
◦ 外层 for 循环依次枚举第⼀个数 a ；
◦ 内层 for 循环依次枚举第⼆个数 b ，让它与 a 匹配；
ps ：这⾥有个魔⻤细节：我们挑选第⼆个数的时候，可以不从第⼀个数开始选，因为 a 前
⾯的数我们都已经在之前考虑过了；因此，我们可以从 a 往后的数开始列举。
◦ 然后将挑选的两个数相加，判断是否符合⽬标值。
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int n = nums.size();
for (int i = 0; i < n; i++) { // 第⼀层循环从前往后列举第⼀个数
for (int j = i + 1; j < n; j++) { // 第⼆层循环从 i 位置之后列举第⼆个数
if (nums[i] + nums[j] == target) // 两个数的和等于⽬标值，说明我们已经找到结果了
return {nums[i], nums[j]};
}
}
return {-1, -1};
}
};解法⼆（双指针-对撞指针）：
算法思路：
注意到本题是升序的数组，因此可以⽤「对撞指针」优化时间复杂度。
算法流程（附带算法分析，为什么可以使⽤对撞指针）：
a. 初始化 left ， right 分别指向数组的左右两端（这⾥不是我们理解的指针，⽽是数组的下
标）
b. 当 left < right 的时候，⼀直循环
i. 当 nums[left] + nums[right] == target 时，说明找到结果，记录结果，并且
返回；
ii. 当 nums[left] + nums[right] < target 时：
• 对于 nums[left] ⽽⾔，此时 nums[right] 相当于是 nums[left] 能碰到的
最⼤值（别忘了，这⾥是升序数组哈~）。如果此时不符合要求，说明在这个数组⾥⾯，没有别的数符合 nums[left] 的要求了（最⼤的数都满⾜不了你，你已经没救了）。因此，我们可以⼤胆舍去这个数，让 left++ ，去⽐较下⼀组数据；
• 那对于 nums[right] ⽽⾔，由于此时两数之和是⼩于⽬标值的， nums[right]
还可以选择⽐ nums[left] ⼤的值继续努⼒达到⽬标值，因此 right 指针我们按兵不动；
iii. 当 nums[left] + nums[right] > target 时，同理我们可以舍去
nums[right] （最⼩的数都满⾜不了你，你也没救了）。让 right-- ，继续⽐较下⼀
组数据，⽽ left 指针不变（因为他还是可以去匹配⽐ nums[right] 更⼩的数的）。
如图所示：
对于升序数组而言，只需要双指针思想，用left表示最小数，用right表示最大数，当两个数字相加时，如果大于要求的值，则right--，否则，left++
编写代码
c++算法代码：
class Solution
{
public:
vector<int> twoSum(vector<int>& nums, int target)
{
int left = 0, right = nums.size() - 1;
while(left < right)
{
int sum = nums[left] + nums[right];
if(sum > target) right--;
else if(sum < target) left++;
else return {nums[left], nums[right]};
}
// 照顾编译器
return {-4941, -1};
}
};java算法代码：
class Solution
{
public int[] twoSum(int[] nums, int target)
{
int left = 0, right = nums.length - 1;
while(left < right)
{
int sum = nums[left] + nums[right];
if(sum > target) right--;
else if(sum < target) left++;
else return new int[] {nums[left], nums[right]};
}
// 照顾编译器
return new int[]{0};
}
}