一、有效三角形的个数
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--; } else begin++; } } 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; } };
