算法每日双题精讲——双指针（有效三角形的个数，和为s的俩个数）

🌟快来参与讨论💬，点赞👍、收藏⭐、分享📤，共创活力社区。 🌟

别再犹豫了！快来订阅我们的算法每日双题精讲专栏，一起踏上算法学习的精彩之旅吧！💪

💯前言

💯有效三角形的个数

题目描述：

⭐解题思路：

🙋这个解题思路是怎么来的呢？

代码实现（C++ 为例）：

👀时间复杂度和空间复杂度

💯和为 s 的俩个数

题目描述：

⭐解题思路：

🙋这个解题思路是怎么来的呢？

代码实现（C++ 为例）：

👀时间复杂度和空间复杂度

💯总结

💯前言

在算法的奇妙世界里，双指针技巧宛如一把神奇的钥匙，能够开启许多难题的解决之门😎。

今日，就让我们一同深入探究两道借助双指针策略破解的经典题目：有效三角形的个数与和为s的俩个数。

📣 由于这两道题目均与数组相关，这里所运用的双指针算法是：利用数组下标代替指针。

当面临数组相关的组合、查找等问题时，双指针法常常能为我们打开解题的新思路。

💯有效三角形的个数

题目链接👉【力扣】

题目描述：

给定一个包含非负整数的数组，你的任务是统计其中可以组成三角形三条边的三元组个数。

示例：

输入: [2,2,3,4]
输出: 3
解释：
有效的组合是:

2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3

⭐解题思路：

对数组排序，方便后续判断。
遍历数组，对于每个元素，使用双指针：一个指针 right 从当前元素后一个位置开始，另一个指针 left 从数组末尾开始。
根据三角形两边之和大于第三边的性质，通过比较当前元素与两个指针指向元素的和来移动指针，并统计满足条件的组合个数。

🙋这个解题思路是怎么来的呢？

我们首先最容易想到解法一：暴力求解

对数组的每三个值进行判断是否满足三角形条件，该方法的时间复杂度为 $O(n^3)$

👇以下是优化的算法：

我们先将数组排序

如果 nums[left]+nums[right]>nums[max] ，那么right左边的所有的俩数相加都大于nums[max]，均满足条件，个数为count = right - left,接着我们让 right-- ，接着找可能的情况
如果nums[left]+nums[right]<=nums[max]，就意味着left与右边任意一个数相加都小于nums[max],因此我们让 left++
直到 left>=right ，结束以max往右的数查找
我们让 max-- ，再次找新的满足条件的值

4+7>10，记录count=7-4=3,然后让right--

完成查找后，让max--，循环这个过程，直到max为数组的第三个数。

代码实现（C++ 为例）：

class Solution {
public:int triangleNumber(std::vector<int>& nums) {// 获取输入数组的长度int n = nums.size();// 用于记录可以组成三角形的三元组数量int count = 0;// 对输入数组进行排序std::sort(nums.begin(), nums.end());// 遍历可能的最长边（从最后一个元素开始，至少需要三条边，所以 max>=2）for (int max = n - 1; max >= 2; max--) {int right = max - 1;int left = 0;// 寻找与当前最长边可以组成三角形的另外两条边while (left < right) {// 如果两条较短边之和大于最长边，可以组成三角形if (nums[left] + nums[right] > nums[max]) {// 因为数组是有序的，所以从 left 到 right - 1 的所有元素与 right 和 max 所指元素都可以组成三角形count += right - left;right--;} else {// 两条较短边之和不大于最长边，left 指针右移，尝试更大的较短边left++;}}}return count;}
};

👀时间复杂度和空间复杂度

时间复杂度：排序为 $O(nlogn)$ ，遍历数组和移动指针为 $O(n^2)$ ，总体约为 $O(n^2)$ 。
空间复杂度： $O(1)$ 。

💯和为 s 的俩个数

题目链接👉【力扣】

题目描述：

给定一个整数数组 nums 和一个目标值 s，在数组中找出和为目标值 s 的那两个整数，并返回它们的数组下标。

假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例：
给定 nums = [2, 7, 11, 15], s = 9
因为 nums [0] + nums [1] = 2 + 7 = 9
所以返回 [0, 1]

⭐解题思路：

先对数组排序。
定义双指针，一个指向数组开头，一个指向末尾。
计算两指针指向元素的和，与目标值比较：相等则找到，返回下标；小于目标值则左指针右移；大于目标值则右指针左移。

🙋这个解题思路是怎么来的呢？

我们首先最容易想到解法一：暴力求解

对数组的每俩个数，进行相加判断和是否为S，因此这种方法的时间复杂度为 $O(n^2)$

👇以下是优化的算法：

我们假设有以下数组：

由于 2+21<30 ,我们让 left++

由于 7+21<30 ,我们让 left++

由于 11+21>30 ,我们让 right--

因为 21+19=30 ，我们返回left,right即可

代码实现（C++ 为例）：

class Solution {
public:std::vector<int> twoSum(std::vector<int>& nums, int s) {// 初始化左指针指向数组开头int left = 0;// 初始化右指针指向数组末尾int right = nums.size() - 1;// 对输入数组进行排序std::sort(nums.begin(), nums.end());while (left < right) {// 计算当前左指针和右指针所指元素之和int sum = nums[left] + nums[right];if (sum == s) {// 如果和等于目标值，返回两个指针所代表的下标return {left, right};} else if (sum < s) {// 如果和小于目标值，左指针右移以尝试更大的元素left++;} else {// 如果和大于目标值，右指针左移以尝试更小的元素right--;}}// 如果没有找到满足条件的两个元素，返回空数组return {};}
};