双指针算法的妙用：提高代码效率的秘密（3）

双指针算法的妙用：提高代码效率的秘密（3）

前言：

小编在昨日讲述了关于双指针算法的两个题目，今日继续分享两个题目的解析，我相信，我只要坚持每天啥刷题，算法能力终究会提高的，下面废话不多说，开始进入今天的代码时间。

正文：

1.有效三角形的个数

1.1.题目来源

老规矩，先展示题目的来源：611. 有效三角形的个数 - 力扣（LeetCode）

1.2.题目讲解

本题是想让我们计算一个区间内有效三角形的个数，各位读者看这个题目的时候不要被这个题目的难度给打败，我们如果一直做简单题是没有什么效果的，难题我们总是会在刷题的路上遇到的，这是不可避免的事，我们早点遇到难题才会为我们以后拿下难题作为基础。这个题目的内容大支架就是这样简单的，当然我们看到例题的时候，可以知道这个题目如果有重复的数出现也是没有问题的，因为此时重复的数出现的位置是不一样的，所以自然可以允许三个数重复，下面小编给出这个题目的思路讲解。

1.3.题目思路解析

这个题目就要让我们具备一定的数学基础，首先的话我们要知道如何去判断一个三角形，这个小学我们就学过，如果有读者朋友不知道那就不应该了：对于一个三角形：任意给出两边，两边之和大于第三遍或者是两边之差小于第三边，那就证明出这个就是个三角形，我们依据这个性质，首先会想到一个解法：暴力解法。

1.3.1.暴力解法

无论我们去做哪个算法题，暴力解法往往是我们第一个可以想到的最容易去解决题目的算法，就以这个题目为例子，我们知道了如何去判断一个三角形，只要我们让任意两边之和大于第三遍即可，那我们就可以选择通过循环来完成这个题目，最外层循环是第一个数，第二个循环是第二个数，第三个循环是第三个数，通过三层循环来做到判断一个三角形，对于三角形的判断，我们可以采取分别判断三边来进行判断的操作，不过这样的时间复杂度会变的很恐怖，所以小编不推荐这个判断三角形的方法，具体三角形的判断方法小编会在一会进行叙述，在这里可以先知道我们仅通过判断一次三个数的比较就可以判断出一个三角形，如此做下去，虽然说没有错误，但是时间复杂度会是O（N ^ 3），这个题目包是通过不了的，所以暴力解法out，下面小编先讲述用数学思想简化判断三角形，然后讲述这个题目最好用的解法。

1.3.2.数学思想简化判断三角形

这个理想其实也是很好像的，我们比较一个三角形的大小，正常是判断任意两边之和大于第三边，下面我们可以这么想：我们先选择一个最大的数，让另外两个数和这个数进行比较，如果大于的话我们可以直接判断这是三角形，反着则不是；关于我为什么说这么做就可以判断三角形，听我娓娓道来：此时我们已经知道两个小的数加起来大于第三个数了，如果正常解法的haul，我们就要用两个数之一和大的数相加与另外一个小的数进行比较了，这样的结果是显而易见是大于的，因为两个小的数都大于大的数了，更何谈小的加大的了？所以我们在判断三角形的时候，仅需把两个小的和大的做比较即可，此时就是这个题目用到的数学思想。

1.3.3.双指针解法

这个题目比较好用的解法，其实还是用到双指针的知识进行求解，此时我们就要借助上面的数学思想了，此时因为我们要知道谁是最大的数，所以我们要让数组进行排序，此时我们调用算法库里面的sort()函数即可，之后我们就要讲述一下我们如何使用双指针来进行有效三角形个数的计算：

首先我们需要先把最后一个数定下来（i），它表示在三角形中最大的数，然后我们设置好两个指针，一个指针（left）代表开头的位置，一个指针表示最后一个数前一个的位置（right），下面我拿例一举例子：

之后我们想让left和right位置的数据相加和最大数位置（i）进行比较，如果此时两数之和大于最大位置的数，那么我们中间位置的三角形就不用计算了，因为此时最左边的数最小，此时的它已经和right相加大于最大的数了，那就更不用说比它大的右边的数了，所以此时我们自己计算中间三角形的个数即可，也就是right - left；倘若两数之和小于大数，那么就让left往右边走，直到找到大于第三遍或者左右指针相遇了，此时就结束查找。以上都做完的话，那么就让最大的数往左走，进行剩余区间三角形个数的查找。就以例一为例，此时left + right大于i，所以我们统计二者之差后，让i往前走，right也会跟着往前走，left还是最小位置：

之后我们进行重复判断完以后就可以找到所有三角形的个数，这就是本题目的思路讲解，下面小编进入代码部分的讲解。

1.4.代码实操

首先，我们需要先给数组排个序，通过sort函数可以轻松解决排序问题，并且设置一个变量来对三角形个数进行计算：

sort(nums.begin(),nums.end());
int count = 0;

之后我们就可以进入主要内容的书写，我们要先完成最大数的循环，此时我们仅需通过一层for循环来解决这个问题，刚开始我们让最大数的位置是数组最后一个位置的数据，然后它的限制条件是它需要大于等于第三个位置的数据，因为第三个位置之前的数在进行判断三角形就完全没有必要了，其代码如下所示：

for(int i = nums.size() - 1 ; i >= 2 ; i--)
{//循环的内容下面讲}

我们在循环体里面就可以进行双指针的书写，其中left是最左位置，right是最大的位置的上一个位置，此时我们还需要用到一个循环，用循环来判断有效三角形的个数，在新的循环体里，我们需要判断此时了left和right之和是否大于最大的数，如果大于的话，我们可以计入它们之间有效三角形的个数，然后结束循环，如果小于的话，让left往右边走，直到left >= right，那么循环结束，此时我们继续进入下一个外层循环，通过双层循环来进行判断有效三角形的个数，此时这个循环体就结束了：

int left = 0,right = i - 1;
while(left < right)
{if(nums[left] + nums[right] > nums[i]){count += right - left;right--;}elseleft++;
}

此时本题目的讲述就结束了，下面我给出完整解题代码，并进入下一个题目的讲述。

1.5.解题代码

class Solution {
public:int triangleNumber(vector<int>& nums) {sort(nums.begin(),nums.end());int count = 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]){count += right - left;right--;}elseleft++;}}return count;}
};

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

2.1.题目来源

老规矩，先给出本题的来源：查找总价格为目标值的两个商品

2.2.题目讲解

本题原来其实是剑指offer的一个题目，我找了类似的题目来给各位进行讲解，这个题目其实理解起来是很容易的，它无非就是让我们在一个严格单增的数组里面找到两个数，让这个数刚好等于给定我们的数target，如果找到了就返回这两个数，没有的话就返回空，下面小编进入题目的思想讲解部分。

2.3.题目思路讲解

2.3.1.暴力解法

同样的，这个题目也是有暴力解法的，小编刚开始想到的解题方法就是通过两个循环进行遍历数组，让第一个循环从开头开始，让第二个循环从第一个数的下一个数开始，开始通过两个循环找到两个数的和等于给定的数target，如果循环结束了，就证明没有找到，我们返回一个空就好，这样的解法虽然想起来和写起来是很容易的，但是这样做的话导致时间复杂度变的非常高，由于两次循环，所以复杂度是O(N ^ 2)，这么做有时候是通不过题目的，我们要学会从题目中找到简单的方法，这里我们可以知道此时的数组是单调递增的，我们可以通过这个性质，加上暴力解法的思想来进行题目的解答，下面小编给出这个题目的优选算法。

2.3.2.双指针解法

本题目其实用双指针做起来是最舒服的，当然，有的读者朋友也可以用二分解法来解决这个问题，不过这个题目，小编还是很推荐用双指针的，此时我们仅需一个循环就可以解决这个问题，双指针的用法如下所示：

1. 首先我们需要两个指针，一个指向开头（left），一个指向结尾（right）。
2. 让开头和结尾相加，如果加起来的数大于目标值target，那么我们就让右边的指针往左走，这么做的原因是因为和此时数组性质有关，此时的数组是单增的，所有右边的数肯定是最大的，此时我们二数之和很大，所以我们让大的数减小；如果此时加起来的数小于target，那么就让左边的数往右走，道理和前面类似，我就不多家赘述了。
3. 最后我们如果找到了两个数，使它们加起来等于target，那么我们直接返回这两个数就好；如果循环结束了，证明没有两个数加来为target，那么我们就返回空就好。

这便是这个题目的思路讲解，希望各位在看完我的思路之后自己敲一遍代码，如果认为我说的不太懂的话，评论区dd我或者直接私信我，我会重新把思路讲解部分写一遍的，来帮助各位理解，下面小编进入代码讲解部分。

2.4.代码实操

首先，我们准备两个指针，一个指向开头（left），一个指向结尾（right），另外我们在设置一个vector容器，用来存储两个数：

vector<int> s1;
int left = 0,right = price.size() - 1;

之后我们就进入一个循环，循环的条件自然是左指针要小于右指针，我们先来判断此时的两数之和和target之间的关系，如果小于的haul，那么让left往右走；如果大于的话，让right往左走；如果相等的haul，让s1存储这两个数，存储结束后直接返回s1即可，如果循环结束以后没有找到两个数的话，那么直接返回s1（此时为空）即可，下面给出相关代码：

while(left < right)
{if(price[left] + price[right] < target)left++;else if(price[left] + price[right] > target)right--;else{s1.push_back(price[left]);s1.push_back(price[right]);return s1;}
}
return s1;

此时这个题目的代码我们就写完了，下面我展示本题目的所有代码：

2.5.解题代码

class Solution {
public:vector<int> twoSum(vector<int>& price, int target) {vector<int> s1;int left = 0,right = price.size() - 1;while(left < right){if(price[left] + price[right] < target)left++;else if(price[left] + price[right] > target)right--;else{s1.push_back(price[left]);s1.push_back(price[right]);return s1;}}return s1;}
};

3.总结

本篇文章到这也就全部结束了，希望各位好好理解我讲述的两道算法题，我会坚持每日两道算法题的更新，希望各位读者朋友在看完以后，如果我文章有一些错误的话，及时在评论区点出或者私信我，我定会及时修改，讲题的时光总是很短暂，那么各位大佬们，我们下一篇文章见啦~