我爱学算法之—— 感受双指针带来的快感（中）

前言：

​ 欢迎来到我爱学算法系列，本篇接着来学习双指针算法

一、有效的三角形个数

题目链接611. 有效三角形的个数 - 力扣（LeetCode）

题目描述

​ 先来看一下题目

题目要求：

给我们一个数组，我们要找出其中可以组成三角形的三条边的三元组个数

题目描述十分简单，我们首先相当直接暴力枚举，依次判断是否满足条件就行了；但是这样时间复杂度就是O(n^3)，我们需要简化一下

算法解析

暴力枚举：

​ 直接三层for循环，暴力枚举出所以的三元组依次判断是否满足条件 缺点： 时间复杂度为O(n^3)，运行会超时。

优化：

​ 我们知道判断是否能构成三角形，需要判断任意两边之和大于第三边（但是，如果我们已经知道较小的两条边之和已经大于第三边了，那是不是就不用继续判断其他的了）

思路：

• 有了上面那个优化我们就首先让数组有序
• 然后从大到小依次选择一个数，再去枚举另外两个数
• 其次，使用双指针算法，枚举另外两个数（如果这两个数相加之和大于第一个数，则conut += （right - left); left++;否则直接right--;
• 最后遍历完数组，count也计数完毕，直接返回即可。

对于双指针算法操作解析：

• 因为数组已经有序，right指向的是较大的数，如果一个数加上这个数还小于第三个数，那其他的数的比right指向的数小，就不需要再进行判断了，所以直接left++；
• ​ left指向的是较小的数，如果一个数加上这个较小的数都大于第三个数，那么那些大于这个较小的数的就不需要判断了，一定满足，就直接计数，然后left++

过程分析：

代码实现

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

    }
};

这里时间复杂度优化到了O(n^2)，可以说很不错了。

二、两数之和

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

题目描述

​ 题目意思就是，给定一个数组price，在这个数组中找到两个数的和等于target ，最后返回这两个数。

算法解析

首先想到的肯定是暴力解法

枚举所有的二元组，找到和为target 的二元组，然后返回。

双指针算法优化：

使用暴力枚举肯定是不行的，这里使用双指针算法优化。

（注意： 题目中已经说了商品价格是升序排序的(数组有序，优先想到使用二分和双指针算法)）。

• 数组有序（如果数组无序，就让它先有序 ），这样，我们使用双指针遍历数组；
• 比较left和right位置的值的和num 与target，如果num>target，那就直接让right--；（因为left指向的是未遍历数中的最小值，right指向的值加上最小值还大于target，那加上其他的值肯定不会等于target，就不用去比较了。）4
• ​ 如果num<target 就left++；（因为right指向的是未遍历数中的最大值，left指向的值加上最大值还小于target，那加上其他的值肯定不会等于target，就不用去比较了。）

过程分析：

代码实现

class Solution {
public:
    vector<int> twoSum(vector<int>& price, int target) {
        //先让数组有序
        sort(price.begin(),price.end());
        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
                break;
        }
        vector<int> ret;
        ret.push_back(price[left]);
        ret.push_back(price[right]);
        return ret;
    }
};

总结：

​ 这个思路还是很重要的，无论是在三数之和，四数之和中都有应用。