经典双指针算法试题（二）

📘北尘_：个人主页
🌎个人专栏:《Linux操作系统》《经典算法试题 》《C++》 《数据结构与算法》

☀️走在路上，不忘来时的初心

---

一、有效三角形的个数

1、题目讲解

2、讲解算法原理

3、代码实现

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

---

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

1、题目讲解

2、讲解算法原理

3、代码实现

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)  right--;else if(sum< target) left++;else break;}return  {price[left],price[right]};  }
};

---

三、三数求和

1、题目讲解

2、讲解算法原理

3、代码实现

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

---

四、四数求和

1、题目讲解

2、讲解算法原理

3、代码实现

class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {sort(nums.begin(),nums.end());int n=nums.size();vector<vector<int>> ret;for(int i=0;i<n;){for(int j=i+1;j<n;){long long  left=j+1,right=n-1,target1=(long long)target-nums[i]-nums[j];while(left<right){int sum=nums[left]+nums[right];if(sum>target1) right--;else if(sum<target1) left++;else {ret.push_back({nums[i],nums[j],nums[left],nums[right]});left++;right--;while(left<right && nums[left]==nums[left-1]) left++;while(left<right && nums[right]==nums[right+1]) right--;}}j++;while(j<n && nums[j]==nums[j-1]) j++;}i++;while(i<n && nums[i]==nums[i-1]) i++;}return ret;}
};

---