一：数组两数之和等于给定值
这里要考虑的细节：
- 索引---这里是从0开始计算还是1开始
- 解的存在与唯一---没有解怎么办？有多个解怎么办
#include<vector> #include<unordered_map> using namespace std; /* 给定一个整形数组nums: 对于该数组的两个索引i,j(i≠j)，使得nums[i]+nums[j]==target(给定的) 求出要求的i,j值-----即函数返回结果 */ /* 思路---将所有元素放入查找表中，之后对每一个元素a，检查target-a的存在性 数据结构---map：k存放元素值，v对应着元素的索引（我们要返回的结果） */ class soluction{ public: vector<int> twoSum(vector<int>& nums,int target){ //函数传入：数组和目标值，返回结果：满足条件的两个索引 unordered_map<int,int> record;//只实现查找，哈希表类型即可 for(int i=0;i<nums.size();i++){ int find_num=target-nums[i]; //在当前的record中查找是否存在满足条件的：find_num if(record.find(find_num)!=record.end()){//找到了 //所求下标为--当前索引，record存放的v值 int res[2]={record[find_num],i}; return vector<int>(res,res+2); } record[nums[i]]=i;//k存放元素值，v存放索引 } throw invalid_argument("no soluction！");//无解，抛出异常 } };测试程序：
#include"two_sum.h" #include<iostream> using namespace std; int main(){ vector<int> arr={1,8,9,4,7,2,6,3,5}; int target=14; vector<int> sum=soluction().twoSum(arr,target); for(int i=0;i<sum.size();i++){ cout<<sum[i]<<" "; } return 0; }注意---数组转换成vector
int ary[]={1,8,9,4,7,2,6,3,5};
vector<int> vec(ary, ary + sizeof(ary) / sizeof(int));
算法思想：
用map作为查找表：k存放元素，i存放索引
由于一次性全部将“元素值-索引”存放map时，如果有相同的元素时会发生覆盖。
所以：每次取一个元素，计算出待查找的值大小，如果没找到，才把该元素放入查找表map中，这时候覆盖就无所谓了，毕竟元素值不会变
二：四个数组中各取一个元素相加为0的所有可能
#include<map> #include<vector> #include<cassert> using namespace std; class soluction{ public: int fourSumTotal(vector<int>& a,vector<int>& b,vector<int>& c,vector<int>& d){ //传入四个数组，返回可能情况的个数 /*题目要求四个数组元素个数相同，所以要设置断言*/ assert(a.size()==b.size()&&a.size()==c.size()&&b.size()==c.size()); /* 代码思路： 首先将数组a和数组b相加的所有和作为:k,出现频次记作：v 然后逐个遍历数组c和数组d，判断是否满足条件 */ //1:创建查找表 map<int,int> record; for(int i=0;i<a.size();i++) for(int j=0;j<b.size();j++) record[a[i]+b[j]]++; //2:遍历求解 int res=0;//返回结果 for(int i=0;i<c.size();i++) for(int j=0;j<d.size();j++) if(record.find(-c[i]-d[j])!=record.end()){ res+=record[-c[i]-d[j]]; } return res; } };#include"4sum.h" #include<vector> #include<iostream> using namespace std; int main(){ vector<int> aa={1,2}; vector<int> bb={-1,-2}; vector<int> cc={5,6}; vector<int> dd={-5,-6}; cout<<soluction().fourSumTotal(aa,bb,cc,dd)<<endl; return 0; }思路很清晰：只要知道了要存什么，即可求出结果
int dist(const pair<int,int>& a,const pair<int,int>& b){ return (a.first-b.first)*(a.first-b.first)+ (a.second-b.second)*(a.second-b.second); } int main(){ vector<pair<int,int>> m={{0,0},{1,0},{2,0}}; cout<<dist(m[0],m[2])<<endl; return 0; }注意：取出整个点，直接用：变量名【下标】
三：点距离相等的可能
思路：
把点i看成一个枢纽，求出所有点到点i的距离：
----------利用map存储，k存放距离，v存放个数
----------只要v大于2就可以找到两个点，剩下的就是排列组合问题
vector存储pair对用法
vector<pair<int,int>> m={{1,2},{2,3},{4,2}}; /*遍历方式*/ //1:下标 for(int i=0;i<m.size();i++){ cout<<m[i].first<<","<<m[i].second<<endl; } //2:迭代器 vector<pair<int,int>>::iterator iter; for(iter=m.begin();iter!=m.end();iter++){ cout<<iter->first<<","<<iter->second<<endl; cout<<(*iter).first<<","<<(*iter).second<<endl; }首先先看：vector<pair<类型，类型>>的遍历方式
第一种：变量名[下标].first//second
第二种：迭代器---（iter*).first//second 或 iter->first//second
int main(){ vector<pair<int,int>> m; m.push_back({1,2}); m.push_back({3,4}); /*遍历方式*/ for(int i=0;i<m.size();i++){ cout<<m[i].first<<","<<m[i].second<<endl; } return 0; }加入元素：push_back({a,b})
首先这里需要对这个基准点做出选择，实际上点i有数组长度种可能，所以每一种可能都要创建一种查找表，然后在查找表内挑出符合题目要求的
int dist(const pair<int,int>& a,const pair<int,int>& b){ return (a.first-b.first)*(a.first-b.first)+ (a.second-b.second)*(a.second-b.second); } int main(){ vector<pair<int,int>> m={{1,1},{1,2},{2,1},{4,5},{5,4}}; for(int i=0;i<m.size();i++){ map<int,int> record;//在循环体内创建查找表 for(int j=0;j<m.size();j++){ if(j != i)//去除自己和自己计算可能 record[dist(m[i],m[j])]++; } //遍历 map<int,int>::iterator iter; for(iter=record.begin();iter!=record.end();iter++){ cout<<iter->first<<","<<iter->second<<endl;} cout<<endl; } return 0; }
完整程序
#include<vector> #include<map> using namespace std; class soluction{ private: //利用距离的平方计算，避免开根号产生误差，影响查找表的查找 int dist(const pair<int,int>& a,const pair<int,int>& b){ return (a.first-b.first)*(a.first-b.first)+ (a.second-b.second)*(a.second-b.second); } public: int sameDist(vector<pair<int,int>>& points){ //传入参数是：pair<int,int>的pair对，存放在vector<>中 int res=0;//记录返回值 for(int i=0;i<points.size();i++){ map<int,int> record;//记录所有点到i的距离 for(int j=0;j<points.size();j++){ if(j!=i) record[dist(points[i],points[j])]++;//别忘了频次累计 } //遍历查找表 map<int,int>::iterator iter; for(iter=record.begin();iter!=record.end();iter++){ if(iter->second>=2) res+=(iter->second)*(iter->second-1); } } return res; } };#include"dist.h" #include<iostream> using namespace std; int main(){ vector<pair<int,int>> m={{1,1},{1,2},{2,1},{4,5},{5,4}}; cout<<soluction().sameDist(m); return 0; }
四：滑动窗口和查找表
思路：
题目要求找两个值相同的索引，且距离不超过k
也就是要找这样一个区间：【l,l+k】使得其中包含两个值相同的索引
存在结束程序，如果区间不存在，那么就看下一个元素
此时要把窗口左移，也就是l加一
如果该元素与左移后的窗口依然没有重复元素，那么纳入该元素，l+k加一
重复上述过程
代码
#include<vector> #include<set> using namespace std; class soluction{ public: bool get_indexes(vector<int>& nums,int k){ set<int> record; for(int i=0;i<nums.size();i++){ //每次访问一个元素，都要判断查找表中是否存在 if(record.find(nums[i])!=record.end()) return true; //不存在加入查找表，此时查找表没重复元素 record.insert(nums[i]); //查看查找表尺寸，过节，删去最最左边元素 if(record.size()==k+1)//ex:0~k是有k+1个数 record.erase(nums[i-k]);//当前i是k,最左边为0 } return false; } };#include"hdwindow.h" #include<iostream> using namespace std; int main(){ vector<int> m={1,2,3,4,5,6,7,2,3}; int k=6; cout<<soluction().get_indexes(m,k); return 0; }
版权声明：本文为weixin_47173597原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。