和为S的两个数

题目解析

【题目链接】

该题目的原题为和为s的两个数:

即给定一组升序数据(数组price),并给出一个变量target,要求找出和为target的两个数;

---

算法原理

• 暴力枚举

  暴力枚举顾名思义就是暴力解法,使用两个for循环枚举出所有的可能并做出判断;

  for(i)
  {for(j){check(i+j==target?)    }
  }
  

• 双指针

  该双指针的解法即为创建两个指针分别为left与right分别指向0与price.size()-1的位置;

  由于数据已经是升序已经具有单调性,所以不需要再进行排序;

  left+right每次的结果sum共有三种可能性:

  1. sum>target;
  2. sum<target
  3. sum==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的两个数的思路进行;

  具体为:

  1. 固定好一个数据(最左),在该数据的右侧区间内找到和为该数的相反数的两个数;

     

  2. 由于需要找到数组中所有这样的数据,所以在找到一组数据后应该继续找;

  同时在该题中应该要特别注意一个细节:

  • 去重

  该数据中返回的所有三元组和都将是不重复的,具体的去重方法有两种:

  1. 使用unordered_set容器进行去重;

  2. 控制指针,当指针所指数据与上一位置数据相同则会出现三元组重复的可能;

     所以分别控制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;}
};

---