当前位置：首页 > article >正文

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

article 2024/11/16 5:34:59

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

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

💯前言

💯有效三角形的个数

题目描述：

⭐解题思路：

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

代码实现（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 {};
    }
};