力扣题库1（map用法笔记，vector笔记）

大家好，欢迎来到IT知识分享网。

2022.9.14

法一：暴力

第一次用力扣的编辑器，代码习惯有点没改过来，慢慢记录刷题过程吧，暴力没啥技巧，刚开始最后面的return忘写了，一直纳闷为啥报错

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int i,j;
        for(i=0;i<nums.size()-1;i++)
        {

            for(j=i+1;j<nums.size();j++)
            {

                if(nums[i]+nums[j]==target)
                    return{i,j};
            }
        }
        return {0,1};
    };
};

法二：哈希表

可以有效降低时间复杂度，map是STL的一个关联容器，能提供一对一数据存储处理，前者称为关键字，每个map只能出现一次该关键字，后者为关键字的值，count的时间复杂度应该是 O(nlogn+(所查询的值的长度)),

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int,int>a;//建立hash表存放元素
        vector<int>b(2,0);
        for(int i=0;i<nums.size();i++)
            a.insert(map<int,int>::value_type(nums[i],i));
        for(int i=0;i<nums.size();i++)
        {
            if(a.count(target-nums[i])>0&&(a[target-nums[i]]!=i))  //能否找到匹配元素且不能是自身
            {
                b[0]=i;
                b[1]=a[target-nums[i]];
                break;
            }
        }
        return b; 
    };
};

后续明天更，加油

2022.9.21

1、map的使用

头文件：#include<map>

map对象是模板类，需要关键字和存储对象两个模板参数：std:map<int,string>personnel

这就形成了int作为索引，拥有相关联的指向string的指针

2、map的构造

map<int,string>mapStudent

3、插入元素

// 定义一个map对象
map<int, string> mapStudent;
 
// 第一种 用insert函數插入pair
mapStudent.insert(pair<int, string>(000, "student_zero"));
 
// 第二种 用insert函数插入value_type数据
mapStudent.insert(map<int, string>::value_type(001, "student_one"));
 
//第一种和第二种效果相同

// 第三种 用"array"方式插入
mapStudent[123] = "student_first";
mapStudent[456] = "student_second";

用insert函数插入数据，在数据的 插入上涉及到集合的唯一性这个概念，即当map中有这个关键字时，insert操作是不能在插入数据的，但是用数组方式就不同了，它可以覆盖以前该关键字对 应的值，用程序说明如下：

mapStudent.insert(map<int, string>::value_type (001, "student_one"));
 
mapStudent.insert(map<int, string>::value_type (001, "student_two"));

map中的001对应是student_one，第二句并没有生效

vector用法：

1、头文件

#include<vector>
using namespace std;

2、一维向量

（1）向量的声明及初始化

vector<int> a;  //声明一个int型向量a
vector<int> a(10);  //声明一个初始大小为10的向量
vector<int> a(10, 1);  //声明一个初始大小为10且初始值都为1的向量
vector<int> b(a); //声明并用向量a初始化向量b
vector<int> b(a.begin(), a.begin()+3); //将a向量中从第0个到第2个(共3个)作为向量b的初始值

//直接使用数组来初始化向量

int n[] = {1, 2, 3, 4, 5};
vector<int> a(n, n+5);  //将数组n的前5个元素作为向量a的初值
vector<int> a(&n[1], &n[4]); //将n[1] - n[4]范围内的元素作为向量a的初值

（2）元素输入及访问

vector<int> a(10); //大小为10的向量a
cin >> a[2];
for(int i = 0; i < a.size(); ++i)
	cout << a[i] << ' ';