2:set和map解决力扣题

一：数组两数之和等于给定值

 这里要考虑的细节：

• 索引---这里是从0开始计算还是1开始
• 解的存在与唯一---没有解怎么办？有多个解怎么办

#include
#include
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;isize();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
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;isize();i++){
        cout<" ";
    }
    return 0;
}

注意---数组转换成vector

    int ary[]={1,8,9,4,7,2,6,3,5};

    vector vec(ary, ary + sizeof(ary) / sizeof(int));

---

算法思想：

用map作为查找表：k存放元素，i存放索引

由于一次性全部将“元素值-索引”存放map时，如果有相同的元素时会发生覆盖。

所以：每次取一个元素，计算出待查找的值大小，如果没找到，才把该元素放入查找表map中，这时候覆盖就无所谓了，毕竟元素值不会变

 二：四个数组中各取一个元素相加为0的所有可能

 

#include
#include
#include
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;isize();i++)
       for(int j=0;jsize();j++)
           record[a[i]+b[j]]++;
    //2:遍历求解
    int res=0;//返回结果
    for(int i=0;isize();i++)
       for(int j=0;jsize();j++)
           if(record.find(-c[i]-d[j])!=record.end()){
              res+=record[-c[i]-d[j]];
           }
    return res;
  }
};

#include"4sum.h"
#include
#include
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)<
    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(){
    vectorint,int>> m={{0,0},{1,0},{2,0}};
    cout<<dist(m[0],m[2])<
    return 0;
}

 注意：取出整个点，直接用：变量名【下标】

 三：点距离相等的可能

 思路：

 把点i看成一个枢纽，求出所有点到点i的距离：

----------利用map存储，k存放距离，v存放个数

----------只要v大于2就可以找到两个点，剩下的就是排列组合问题

vector存储pair对用法 

vectorint,int>> m={{1,2},{2,3},{4,2}};
    /*遍历方式*/
    //1:下标
    for(int i=0;isize();i++){
		cout<","<
	}
    //2:迭代器
    vectorint,int>>::iterator iter;
    for(iter=m.begin();iter!=m.end();iter++){
		cout<first<<","<second<
        cout<<(*iter).first<<","<<(*iter).second<
	}

 首先先看：vector<pair<类型，类型>>的遍历方式

第一种：变量名[下标].first//second

第二种：迭代器---（iter*).first//second 或 iter->first//second

int main(){
    vectorint,int>> m;
    m.push_back({1,2});
    m.push_back({3,4});
    /*遍历方式*/
    for(int i=0;isize();i++){
		cout<","<
	}
    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(){
     vectorint,int>> m={{1,1},{1,2},{2,1},{4,5},{5,4}};
     for(int i=0;isize();i++){
          map<int,int> record;//在循环体内创建查找表
          for(int j=0;jsize();j++){
            if(j != i)//去除自己和自己计算可能
              record[dist(m[i],m[j])]++;
          }
          //遍历
          map<int,int>::iterator iter;
          for(iter=record.begin();iter!=record.end();iter++){
          cout<first<<","<second<
          cout<
     }
    return 0;
}

 

完整程序

#include
#include
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(vectorint,int>>& points){
      //传入参数是：pair的pair对，存放在vector<>中
      int res=0;//记录返回值
      for(int i=0;isize();i++){
        map<int,int> record;//记录所有点到i的距离
        for(int j=0;jsize();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
using namespace std;
int main(){
    vectorint,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
#include
using namespace std;
class soluction{
public:
    bool get_indexes(vector<int>& nums,int k){
    set<int> record;
    for(int i=0;isize();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
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;
}