算法入门：专题攻克一---双指针（3）有效三角形的个数 查找总价格为目标值的两个商品（剑指offer题目）

有效三角形的个数

有效三角形的个数

题目解析：

数组中随意挑出三个数字，挑出所有可以组成三角形的组合，最终仅仅需要返回所有三元组的个数即可。

算法原理：

三角形的组成：两边之和大于第三边，两边之差小于第三边。那如果按照这种规则拿出所有的组合，再将所有组合进行判断，这个时间复杂度可能会很大，那么要减少时间的消耗，就需要先对三个数字进行排序，只需要较小的两个数字相加大于第三个数字就满足构成三角形的条件了。

优化：先对整个数组进行排序

解法一：暴力解法，三层枚举

解法二：排序之后，利用单调性，使用双指针算法来解决问题。先来固定最大的数字，这里给一个数组我们好理解，[ 2, 2, 3, 4, 5, 9, 10],先固定第三边c=10，然后将定义两个指针，left先从索引为0的元素开始，假设left所在的数字数值为a，right是C之前的索引为n-2的元素，指向第二大的元素，right所在的数字数值为b，如果最小的元素数值跟第二大的元素数值相加大于最大的数值，那么此时2之后的元素跟9相加都会大于10，此时有right-left组可以构成a+b>c的三角形组合。 接下来将right--，向前挪动一位，如果a+b都是小于等于c的，找不到结果，然后left++，接着重复我们上面的操作，

解法总结：

1.先固定最大的数； 2.在最大的数的区间中，使用双指针算法，快速统计出符合要求的三元组的个数；

接下来我们将思路转化成代码： 先对整个数组 进行排序，sort(nums.begin(),nums.end()); 整个题目最后让我们统计出符合条件的三元组的个数，所以定义一个ret来存储符合条件的三元组的个数，最后返回ret即可； 接着需要利用双指针来统计符合元素的三元组，在此之前需要有一个数组中大的数字充当c,但是这个C不是固定的，让c从数组最后一个元素向前遍历到索引为2的数字，for(int i=n-1;i>=2;i--) 接着让left指针向后遍历，right向前遍历，

• a+b>c: 如果left指向的位置的数字加上right指向的位置的数字大于c,那么从left所在位置直到right所在位置之前这一段区间的数字加上right都大于c，都满足三元组的条件，ret+=right-left，right–;
• a+b<=c:left指向位置的数字加right指向位置的数字小于c,说明left太小了，left++;继续进行判断。最终left>=right时结束循环。

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        //1.优化
        sort(nums.begin(),nums.end());
        //2.利用双指针解决算法问题
        int ret=0;//统计三元组
        int n=nums.size();
        //固定一个最大的数字作为c
        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;
    }
};

查找总价格为目标值的两个商品（剑指offer题目）

查找总价格为目标值的两个商品

题目解析：

这个题我们可以看成是要找出来数组中两个相加等于target的数字。 输入一个递增排序的数组和一个数字s，也就是说数组中的数字是有序的，将数组中相加等于s的两个数字组合输出即可。

算法原理：

解法一：暴力解法 暴力枚举策略：将数组中的所有组合都枚举出来，用两层for循环，伪代码展示： for(int i=0;i<n;i++) for(int j=i+1;j<n;j++) 这样做的不好处就是时间复杂度会上升。

解法二：利用单调性，使用双指针算法解决问题

将left放置在索引为0的位置，right放置在n-1的位置，这里给一个详细的例子数组[ 2 7 11 15 19 21 ],target为30，首先left是指向2的位置，right放置在21的位置，此时left+right，sum值小于target,最小的数字和最大的数字相加都小于target，那么就说明这个最小的数字跟其他数字相加也会小于target，利用单调性的知识我们可以明白，此时就是说left太小了，所以需要left++,换一个更大一点的数字进行相加的对比；所以将left指向7的位置，right指向21，相加还是小于target,接着让left指向11，让right指向21，相加此时发现大于target，也就是说此时的right太大了，让right--到下一个位置；此时left等于11，right=19，相加等于target，符合要求，返回即可。

下面我们就将思路转换为代码写出OJ题；

这道题目最后要让我们找出数组中两个相加等于target的数字，而且任意返回一对就好，我们用双指针算法解决这个问题，定义left=0,right=nums.size()-1;分别找到left和right的初始位置，接着定义一个sum存储相加之后的值，将sum跟target进行对比，

• sum>target:说明right太大了，right--;
• sum<target:说明left太小了，left++;
• sum=target:返回nums[left],nums[right]

但是由于题目中没有给出一整个数组中都找不到两个相加等于target的数，原则上我们已经完成了题目的要求，但是提交代码的时候还会报错，所以要考虑一下编译器，最后我们任意返回两个值，假设编译器没有找到符合条件的值。return{-1,-1};大括号里可以是任意的值。

上代码！

class Solution {
public:
    vector<int> twoSum(vector<int>& price, int target) {
       
        int left=0,right=price.size()-1;
        
        while(left<right)
        {
            int sum=price[left]+price[right];
            if(sum<target) left++;
            else if(sum>target) right--;
            else return {price[left],price[right]};
        }
       //并不是所有题目都有返回值,这里需要照顾一下编译器
       return{-1,-1};
    }
};