Leetcode 611 有效三角形的个数
来看看给出的测试用例：
- 输入: nums = [2,2,3,4]
- 输出: 3
- 解释:有效的组合是:
2,3,4 (使用第一个 2)2,3,4 (使用第二个 2)2,2,3
根据题目和样例，这是一个看起来十分简单的题目，让小学生来解决也有可能，毕竟大家都会使用最直接了当的暴力解法，遍历整个数组，筛选出满足的三角形即可。下面我们使用伪代码来简单写一下思路：
for(int i = 0;i < n - 2; i++){ for(int j = i + 1 ; j < n - 1; j++){ for(int k = j + 1 ;k < n;k++){ check(num[i],num[j],num[k]); } } }
很显然，这样的算法时间复杂度是O( n^ 3)，非常非常非常不理想。
那如何把双指针使用到里面呢？
首先我们来看check的过程：
思路与算法
对于正整数 a,b,c它们可以作为三角形的三条边，当且仅当：
a+b>c a+c>b b+c>a
均成立。如果我们将三条边进行升序排序，使它们满足 a≤b≤c，那么 a+c>b 和b+c>a 使一定成立的，我们只需要保证 a+b>c。所以我们只需要比较较小的两个数和最大是否满足即可。
所以现在我们有了一个初步的想法：
- 先对容器元素进行排序
- 从最大值开始依次作为最大值 num1 来找三角形
- 这时开始使用双指针的思想，分别取0（
left）下标位置的 num2 和 num1 左边第一个(right)元素 num3,进行比较 - 使用单调性判断：
- 如果 num2 + num3 > num1 三角形成立，则left 到 right之间的元素都满足 （根据单调性判 断）
- 如果 num2 + num3 <= num1那么三角形不成立，那么就要右移 left 来使 num2 + num3更大一些，
- 依次往复，就解决问题了。
来看代码：
//比较函数 int compare(int i,int j){ return i < j; } class Solution { public: int triangleNumber(vector<int>& nums) { //首先排序，优化容器 //取一个固定的较大数 //在左区间进行查找,利用单调性 sort(nums.begin(),nums.end(),compare); int count = 0; int m = nums.size() - 1; while(m >= 2){ int max = nums[m]; int left = 0,right = m - 1; while(left <= right){ //左值是0直接跳过 //右值是零直接跳出循环（有0不可能成立） if(nums[right] == 0) break; while (nums[left] == 0) left++; int sum = nums[left] + nums[right]; if(sum > max) { count += right - left; right--; } else left++; } //每次m 需要进行移动。 m--; } return count; } };
这样我们就成功解决了问题。来看运行的效果：
击败 93.48%，我们非常快速！！！（如果使用暴力算法，就直接超时了）
所以双指针的算法是非常高效的算法，并且一般有序问题都可以进行求解！
Leetcode LCR179.查找总价格为目标值的两个商品
这道题是十分经典的题目，来自剑指offer 的和为 s 的两个数，让我们来看看吧
根据题目描述，也是比较简单的问题，我们一样来进行单调性分析：
- 首先也是进行排序
- 使用两个指向
leftnum1 和rightnum2 分别从左右开始 - 来分析结果：
- num1 + num2 == target 直接返回即可
- num1 + num2 > target 说明较大，那么right左移即可
- num1 + num2 < target 说明较小，那么left右移即可
- 直到找到结果就好
来看代码：
class Solution { public: vector<int> twoSum(vector<int>& price, int target) { //分别从左右开始遍历 int left = 0; int right = price.size()-1; while(left < right){ int sum = price[left] + price[right]; //三种结果分析好 if(sum > target) right--; else if(sum < target) left++; //返回vector类型 ，使用 { } 包括即可 else return{price[left] , price[right]}; } //照顾编译器，不然报错 return {-1,-1}; } };
我们这样也成功通过测试用例，完成题目！！！
思路非常直接了当。
Leetcode 15.三数之和
我们先来看给出的样例：
- 输入：nums = [-1,0,1,2,-1,-4]
- 输出：[[-1,-1,2],[-1,0,1]]
- 解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。
根据我们的最直接的想法就是遍历，但是我们都知道这样十分复杂，哈哈哈哈
我们来看这道题和判断三角形是不是很像，三角形是要求num1 + num2 > num3,
而这题要求我们num1 + num2 == num3，所以基础的双指针框架是十分相似的，我们可以先写出一个框架来：
class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { //先使数据有序 sort(nums.begin(),nums.end()); vector<vector<int>> ans; //开始遍历，取最大数 int m = nums.size() - 1; //从 最大值 开始 while(m >= 2){ int left = 0 , right = m - 1; int num1 = nums[m]; //双指针进行 while(left < right){ //左值右值进行初始化 int num2 = nums[left] , num3 = nums[right]; //进行判断 if(num2 + num3 + num1 == 0){ //满足就进行插入 ans.push_back({num2,num3,num1}) ; left++; right--; } else if(num2 + num3 + num1 < 0) { left++; } else if(num2 + num3 + num1 > 0) { right--; } } //m 向左移动 m--; } return ans; } };
这样提交后：我们只看这一个样例： 
发现有好多重复的，这应该怎麽办？？？？？？
我的想法是从根源出发，既然我们排好序了就直接每次选中一组后，把相应元素都跳过！！！
不满足的也一次性全部都跳过！！！直接了当
这样一定一定不会有重复的出现！！！
class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { //先使数据有序 sort(nums.begin(),nums.end()); vector<vector<int>> ans; //从最大值开始遍历 int m = nums.size() - 1; while(m >= 2){ //左右值进行初始化 int left = 0 , right = m - 1; int num1 = nums[m]; while(left < right){ int num2 = nums[left] , num3 = nums[right]; if(num2 + num3 + num1 == 0){ ans.push_back({num2,num3,num1}) ; //满足条件直接全部都跳过！！！ while(nums[left] == num2 && left < right){ left++; } while(nums[right] == num3 && left < right){ right--; } } else if(num2 + num3 + num1 < 0) { //不满足条件的都跳过!!! while(nums[left] == num2 && left < right){ left++; } } else if(num2 + num3 + num1 > 0) { //不满足条件的都跳过!!! while(nums[right] == num3 && left < right){ right--; } } } //满足的 m 也都跳过！！！ while(nums[m] == num1 && m > 0){ m--; } } return ans; } };
这样我们完成里去除重复的元素！！！！！！
把最复杂的问题简化到了每个步骤里面：
来看效果：
还不错！！！
送给大家一句话：
如今我努力奔跑，不过是为了追上那个曾经被寄予厚望的自己 —— 约翰。利文斯顿
