和为S的两个数
题目解析
该题目的原题为和为s的两个数:
即给定一组升序数据(数组price),并给出一个变量target,要求找出和为target的两个数;
算法原理
- 暴力枚举
暴力枚举顾名思义就是暴力解法,使用两个for循环枚举出所有的可能并做出判断;
for(i) { for(j) { check(i+j==target?) } }
- 双指针该双指针的解法即为创建两个指针分别为
left与right分别指向0与price.size()-1的位置;由于数据已经是升序已经具有单调性,所以不需要再进行排序;left+right每次的结果sum共有三种可能性:
sum>target;sum<targetsum==target
- 若是
sum>target则表示right数据较大,应该--right;
若是sum<target则表示left数据较小,应该++left;
否则则相等,返回对应的left与right所对应的值;
代码
- 双指针
class Solution { public: vector<int> twoSum(vector<int>& price, int target) { int first = 0; int last = price.size()-1; while(first<last){ if(price[first]+price[last]>target) --last; else if(price[first]+price[last]<target) ++first; else return {price[first],price[last]}; } return {1,2}; } };
三数之和
题目解析
本题的关键信息:
a,b,c三数之和为0;- 不重复的三元组
以示例1为例,三元组为[-1,0,1],[-1,0,1],[-1,-1,2];
但最终答案为[[-1,0,1],[-1,-1,2]];
算法原理
- 双指针该算法原理可以参考上一题
和为S的两个数,具体的思路为将数组首先进行一次排序使其具有单调性;再通过和为S的两个数的思路进行;具体为:
- 固定好一个数据(最左),在该数据的右侧区间内找到和为该数的相反数的两个数;
- 由于需要找到数组中所有这样的数据,所以在找到一组数据后应该继续找;
- 同时在该题中应该要特别注意一个细节:
- 去重
- 该数据中返回的所有三元组和都将是不重复的,具体的去重方法有两种:
- 使用unordered_set容器进行去重;
- 控制指针,当指针所指数据与上一位置数据相同则会出现三元组重复的可能;
所以分别控制cur,lefy,right指针即可;
- 小优化:由于数据经排序后已经具有单调性,所以当
cur所指位置数据>0时,则代表cur后区间的数据中已经不满足三数之和>0,所以cur所指位置数据>0时,可以直接跳出循环;
代码
- 双指针
class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { vector<vector<int>> ret; sort(nums.begin(),nums.end());//排序使数组具有单调性 int len = nums.size(); int cur = 0; while(cur<nums.size()){//固定一个数据 if(nums[cur]>0) break;//当cur数据>0时则表示该指针后的区间不存在符合条件的三元组 //定义变量 int left = cur+1;//left指针所在数据为cur指针后一个位置 int right = nums.size()-1; int targe = -nums[cur];//变量targe用于存储cur所指数据的相反数,用来与左右数据之和进行比较 while(left < right){ int sum = nums[left] + nums[right]; if(sum > targe) --right; else if(sum < targe) ++left; else{ ret.push_back({nums[cur],nums[left],nums[right]}); ++left,--right;//存入一组数据之后应该继续遍历 //对left,right指针进行去重 while(left<right && nums[left-1] == nums[left]) ++left; while(left<right && nums[right+1] == nums[right]) --right; } } ++cur; while(cur<nums.size()&&nums[cur] == nums[cur-1]) ++cur;//对cur进行去重 } return ret; } };
四数之和
题目解析
算法原理
- 双指针
该题的双指针的思路与三数之和题目大差不差,与之不同的是多一层循环用来固定双指针外的另一个数;
代码
class Solution { public: vector<vector<int>> fourSum(vector<int>& nums, int target) { sort(nums.begin(),nums.end());//排序使其具有单调性 vector<vector<int>> ret; int len = nums.size(); for(int i = 0;i<len;){ for(int j = i+1;j<len;){ int left = j + 1; int right = len - 1; long long tmp = (long long)target - nums[i] - nums[j];//long long类型为对测试用例的进行特殊处理 while(left<right){ int sum = nums[left]+nums[right]; if(sum>tmp) right--; else if(sum<tmp) left++; else { ret.push_back({nums[left],nums[right],nums[i],nums[j]}); left++,right--;//继续遍历 //去重左右 while(left<right && nums[left] == nums[left-1]) ++left; while(left<right && nums[right] == nums[right+1]) --right; } } //指针j的去重 ++j; while(j<len&&nums[j] == nums[j-1]) ++j; } //指针i的去重 ++i; while(i<len&&nums[i] == nums[i-1]) ++i; } return ret; } };
