LeetCode -1. 两数之和

谁践踏了优雅 2022-05-23 00:30 172阅读 0赞

给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。

你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。

示例:

给定 nums = [2, 7, 11, 15], target = 9
    
    因为 nums[0] + nums[1] = 2 + 7 = 9
    所以返回 [0, 1]

//暴力解法
    #include <stdio.h>
    #include <stdlib.h>
    #include <malloc.h>
    #include <string.h>
    
    //nums-指向输入进来的数组的指针
    //numSize-数组的长度大小
    //target-找出其中两个数满足相加等于你指定的目标数字
    
    //return返回的方法-形参改变实参
    int *twoSum(int *nums, int numSize, int target)
    {
    	//返回出去的是找到的整型数组的下标的两个数 能满足两个之和等于我们指定的目标数字
    	int *answer = (int *)malloc(sizeof(int) * 2);
    	memset(answer,0,sizeof(int));
    	// 循环其后面的数据看nums[left] + nums[right] == target是否成立
    	// 其实就是看target - nums[right]在不在数组中
    	for (int left = 0; left < numSize; left++)
    	{
    		for (int right = left + 1; right < numSize; right++)
    		{
    			if ((nums[left] + nums[right] ) == target)
    			{
    				answer[0] = left;
    				answer[1] = right;
    				break;
    			}
    		}
    	}
    	return answer;
    }
    
    int main(void)
    {
    	int nums[5] = { 2, 7, 11, 15 };
    	int *answer = NULL;
    	answer = twoSum(nums, 3, 9);
    	printf("[%d, %d]\n", answer[0], answer[1]);
    	system("pause");
    	return 0;
    }

复习：标准库vector

//标准库vector类型是C++中使用较多的一种类模板，vector类型相当于一种动态的容器，在vector中主要有一些基本的操作，接下来分别从以下的几个方面总结：
    //
    //vector对象的定义和初始化
    //vector对象的基本操作，主要包括添加元素，遍历等
    //1、vector对象的定义和初始化
    //在vector中主要有四种定义和初始化的方法：
    //1.1、定义空的vector
    //定义的方法为：
    //vector<T> v;
    
    //1.2、定义一个vector的副本
    //定义的方法为：
    //vector<T> v1(v);
    
    //1.3、定义并初始化
    //定义的方法为：
    //vector<T> v2(n, i);
    //定义了长度为n的vector v2，并且每个元素都是i。
    
    //1.4、定义并指定初始长度
    //定义的方法为：
    //vector<T> v3(n);
    //采用的初始化方法为默认初始化。
    //1 、基本操作
    //
    //(1)头文件#include<vector>.
    //
    //(2)创建vector对象，vector<int> vec;
    //
    //(3)尾部插入数字：vec.push_back(a);
    //
    //(4)使用下标访问元素，cout << vec[0] << endl; 记住下标是从0开始的。
    //
    //(5)使用迭代器访问元素.
    //
    //vector<int>::iterator it;
    //
    //for (it = vec.begin(); it != vec.end(); it++)
    //
    //cout << *it << endl;
    //
    //(6)插入元素：    vec.insert(vec.begin() + i, a); 在第i + 1个元素前面插入a;
    //
    //(7)删除元素：    vec.erase(vec.begin() + 2); 删除第3个元素
    //
    //vec.erase(vec.begin() + i, vec.end() + j); 删除区间[i, j - 1]; 区间从0开始
    //
    //(8)向量大小:vec.size();
    //
    //(9)清空 : vec.clear();
    #include <stdio.h>
    #include <vector>
    using namespace std;
    
    int main01(){
    	//第一种定义方法
    	vector<int> v;//初始状态为空
    	for (int i = 0; i < 10; i++){
    		v.push_back(i);//向其中添加元素，负责把一个值当成vector对象的尾元素“压到push”vector对象的“尾端(back)”
    	}
    
    	//第二种定义方法
    	vector<int> v1(v);//v1中包含v所以元素的副本
    	//第三种定义方法
    	vector<int> v2(10, 1);//v2有10个元素,每个值都是1
    	//第四种定义方法
    	vector<int> v3(10);//v3有10个元素,每个元素的值都是0
    
    	printf("first: ");//v.size()返回v中元素的个数
    	for (vector<int>::size_type ix = 0; ix != v.size(); ix++){
    		printf("%d\t", v[ix]);
    	}
    	printf("\n");
    	printf("second: ");//vector对象的下标运算符可用于访问已经存在的元素,而不能用于添加元素
    	for (vector<int>::size_type ix1 = 0; ix1 != v1.size(); ix1++){
    		printf("%d\t", v1[ix1]);
    	}
    	printf("\n");
    	printf("third: ");
    	for (vector<int>::size_type ix2 = 0; ix2 != v2.size(); ix2++){
    		printf("%d\t", v2[ix2]);
    	}
    	printf("\n");
    	printf("forth: ");
    	for (vector<int>::size_type ix3 = 0; ix3 != v3.size(); ix3++){
    		printf("%d\t", v3[ix3]);
    	}
    	printf("\n");
    	system("pause");
    	return 0;
    }
    //2、vector中的基本操作
    //在vector中的基本操作包括插入，删除，遍历等。
    //2.1、插入操作
    //在vector中插入元素包括两种，一种是在尾部添加元素，使用的函数是push_back()函数，另一种是在指定位置插入元素，使用到的函数是insert()函数。
    //其中，insert()函数的具体形式为：
    //insert(p, t)
    //指的是在迭代器p之前插入值为t的元素。具体应用如下面的例子：
    
    
    int main02(){
    	vector<int> v;//初始状态为空
    	for (int i = 0; i < 10; i++){
    		v.push_back(i);
    	}
    
    	for (vector<int>::size_type ix = 0; ix != v.size(); ix++){
    		printf("%d\t", v[ix]);
    	}
    	printf("\n");
    
    	//在开始前插入10
    	//iterator insert(const_iterator _Where, _Ty&& _Val)
    	v.insert(v.begin(), 10);
    	for (vector<int>::size_type ix = 0; ix != v.size(); ix++){
    		printf("%d\t", v[ix]);
    	}
    	printf("\n");
    
    	//在10和0之间添加11
    	vector<int>::iterator it;//迭代器
    	for (it = v.begin(); it != v.end(); it++){
    		if (*it == 0){
    			v.insert(it, 11);//0前插入操作11
    			break;
    		}
    	}
    	for (vector<int>::size_type ix = 0; ix != v.size(); ix++){
    		printf("%d\t", v[ix]);
    	}
    	printf("\n");
    	system("pause");
    	return 0;
    }
    //2.2、删除操作
    //使用erase()方法删除指定的元素。
    //erase(p)
    //删除迭代器p所指向的元素。
    int main03(){
    	vector<int> v;
    	for (int i = 0; i < 10; i++){
    		v.push_back(i);
    	}
    
    	for (vector<int>::size_type ix = 0; ix != v.size(); ix++){
    		printf("%d\t", v[ix]);
    	}
    	printf("\n");
    
    	//在开始插入10,10,10
    	//iterator insert(const_iterator _Where, size_type _Count,	const _Ty& _Val)
    	//在_Where前插入_Count个数的_Val值
    	v.insert(v.begin(), 3, 10);
    	for (vector<int>::size_type ix = 0; ix != v.size(); ix++){
    		printf("%d\t", v[ix]);
    	}
    	printf("\n");
    
    	//删除第二个10
    	int i = 0;
    	vector<int>::iterator it;
    	for (it = v.begin(); it != v.end(); it++){
    		i++;
    		if (i == 2){
    			v.erase(it);
    			break;
    		}
    	}
    
    	for (vector<int>::size_type ix = 0; ix != v.size(); ix++){
    		printf("%d\t", v[ix]);
    	}
    	printf("\n");
    	system("pause");
    
    	return 0;
    }
    //除此之外，还有clear()方法，清空vector中的所有元素，pop_back()方法，删除末尾的元素
    int main04(){
    	vector<int> v;
    	for (int i = 0; i < 10; i++){
    		v.push_back(i);
    	}
    
    	for (vector<int>::size_type ix = 0; ix != v.size(); ix++){
    		printf("%d\t", v[ix]);
    	}
    	printf("\n");
    
    	//删除末尾元素
    	v.pop_back();
    
    	for (vector<int>::size_type ix = 0; ix != v.size(); ix++){
    		printf("%d\t", v[ix]);
    	}
    	printf("\n");
    
    	system("pause");
    	return 0;
    }
    //2.3、遍历
    //遍历通常有两种方式：
    //通过下标
    //利用迭代器
    int main(){
    	vector<int> v;
    	for (int i = 0; i < 10; i++){
    		v.push_back(i);
    	}
    	//利用下标 注意一定得是访问已存在的元素,而不能用于添加元素     
    	for (vector<int>::size_type ix = 0; ix != v.size(); ix++){
    		printf("%d\t", v[ix]);
    	}
    	printf("\n");
    
    	//利用迭代器
    	vector<int>::iterator it;
    	for (it = v.begin(); it != v.end(); it++){
    		printf("%d\t", *it);
    	}
    	printf("\n");
    
    	system("pause");
    	return 0;
    }

迭代器的简介   
（1）：迭代器类似于指针类型，它也提供了对对象的间接访问。   
（2）：指针是c语言中就有的东西，迭代器是c++中才有的，指针用起来灵活高效，迭代器功能更丰富些。   
（3）：迭代器提供一个对容器对象或者string对象的访问的方法，并且定义了容器范围。

使用迭代器   
迭代器和指针不一样，容器和string有迭代器类型同时拥有返回迭代器的成员。比如，容器都有的成员begin和end，其中begin成员复制返回指向第一个元素（第一个字符）的迭代器，而end成员返回指向容器（或string对象）尾元素的下一个位置的迭代器，也就是说end指示的是一个不存在的元素，所以叫end返回的是尾后迭代器。一般我们清楚一个迭代器的准确类型是什么，所以我们都是使用auto或者decltype来定义变量的。

vector<int> v;
    auto b=v.begin();
    decltype(v.begin()) b=v.begin();

*  1
 *  2
 *  3

标准容器迭代器的运算符

*iter      返回迭代器iter所指元素的引用
    iter->men  解引用iter并获得该元素的名为men的成员,相当于（*iter）.men
    ++iter      令iter指示容器的下一个元素
     --iter      令iter指示容器的上一个元素
    iter1==iter2  如果两个迭代器指示的是同一个元素或者它指向同一个容器的尾后迭代器，则相等.

#include<iostream>
    using namespace std;
    #include<vector>
    int main()
    {
        vector <int> v(10, 1);
        int i=1;
        cout << "未修改前：";
        for (auto v_quote : v)
        {
            cout << v_quote << " " ;   //未修改前
        }
        cout << endl;
        for (auto v_quote = v.begin(); v_quote != v.end(); ++v_quote)
        {
            *v_quote += i;
            ++i;
        }
        cout << "修改后：";
        for (auto v_quote : v)
        {
            cout << v_quote << " ";
        }
        cout << endl;
        system("pause");
        return 0;
    }

![70][]

迭代器的类型   
那些拥有迭代器的标准库类型都是使用：iterator和const\_iterator来表示迭代器的类型：

vector <int> ::iterator it;        //it能读写vector<int>的元素
        vector <int>::const_iterator it;  //it只能读vector<int>的元素，不可以修改vector<int>中的元素
    
        string::iterator s;               //s可以读写string对象中的元素
        string::const_iterator s;          //s只可以读string对象中的元素，不可以修改string对象中的元素

*  1
 *  2
 *  3
 *  4
 *  5
 *  6

const\_iterator和常量指针一样，只可以读取但不可以修改所指的值。在c++11的新标准中，为了便于得到const\_iterator类型的返回值，引入两个新的函数，分别是cbegin和cend,功能类似于begin和end，只是返回的值类型为const\_iterator;

vector动态增长的限制：   
（1）：不能再范围for循环中向vector对象添加元素。   
（2）：任何一种可能改变vector容量的操作，比如push\_back,都会使该vector对象的迭代器失效。

迭代器的运算

iter+n           //迭代器加上一个整数值仍得到一个迭代器，迭代器指示的新位置向前移动了，指示可能是容器的一个元素或者是尾部的下一个位置
    iter-n          //相反，迭代器指示的位置向后移动了，指示可能是容器的一个元素或者是尾部的下一个位置
    iter1+=n   //等价于iter1+n
    iter1-=n    //等价于iter2-n
    iter1-iter2  //两个迭代器的距离，
    >，<,>=,<= //位置离begin近的较小

*  1
 *  2
 *  3
 *  4
 *  5
 *  6

两个迭代器返回的值，在string和vector都为它定义了一个新的类型–difference\_type,它是一个带符号的整型。

#include <iostream>
    #include <vector>
    #include <unordered_map>
    
    using namespace std;
    class Solution
    {
    
    public:
    	vector<int> twoSum(vector<int> &nums, int target)
    	{
    		unordered_map<int, int> unmap;
    		vector<int> res;
    		//[查找元素是否存在]
    		//若有unordered_map<int, int> mp; 查找x是否在map中
    		//方法1 : 若存在  mp.find(x) != mp.end()
    		//方法2 : 若存在  mp.count(x) != 0
    		//用哈希表来做
    		for (int i = 0; i < nums.size(); i++)//对于数组中的每个数据
    		{
    			//nums中就存在两个数和为target
    			if (unmap.count(target - nums[i]))//在unmap中找到9-7=2 也就是看
    			{
    				res.push_back(unmap[target - nums[i]]);//2 对于的index
    				res.push_back(i);//将当前index--7 插入到vector
    				break; 
    			}
    			//无序映射表（Unordered Map）容器是一个存储以键值对组合而成的元素的关联容器（Associative container），容器中的元素无特别的次序关系。该容器允许基于主键地快速检索各个元素
    			//key  --- value
    			unmap[nums[i]] = i;//建立HashMap映射 2对于的index
    		}
    		return res;
    	}
    
    };
    
    int main()
    {
    	vector<int> numbers = {11,15,2,7};
    	int target = 9;
    	Solution solu = Solution();
    	cout << "[" << solu.twoSum(numbers, target)[0] << "," << solu.twoSum(numbers, target)[1] << "]" << endl;
    
    	system("pause");
    	return 0;
    }

unordered\_map是一个关联容器，存储key,value.其中元素并没有特别的次序关系   
特点：   
1. 关联容器中的元素是通过主键（Key）而不是它们在容器中的绝对位置来引用的。   
2. 无序（Unordered）无序容器通过 hash 表来组织它们的元素，允许通过主键快速地访问元素。   
3. 映射（Map）每个元素为一个值（Mapped value）绑定一个键（Key）：以主键来标志主要内容等于被映射值的元素。   
4. 键唯一（Unique keys）容器中不存在两个元素有相同的主键。   
5. 能够感知内存分配器的（Allocator-aware）容器使用一个内存分配器对象来动态地处理它的存储需求。

在 unordered\_map 内部，元素不会按任何顺序排序，而是通过主键的 hash 值将元素分组放置到   
各个槽（Bucket，也可译成“桶”）中，这样就能通过主键快速地访问各个对应的元素   
（平均耗时为一个常量，即时间复杂度为 O(1)）。

## 成员函数 ##

=================迭代器=========================   
begin 返回指向容器起始位置的迭代器（iterator）   
end 返回指向容器末尾位置的迭代器   
cbegin 返回指向容器起始位置的常迭代器（const\_iterator）   
cend 返回指向容器末尾位置的常迭代器   
=================Capacity================   
size 返回有效元素个数   
max\_size 返回 unordered\_map 支持的最大元素个数   
empty 判断是否为空   
=================元素访问=================   
operator\[\] 访问元素   
at 访问元素   
=================元素修改=================   
insert 插入元素   
erase 删除元素   
swap 交换内容   
clear 清空内容   
emplace 构造及插入一个元素   
emplace\_hint 按提示构造及插入一个元素   
================操作=========================   
find 通过给定主键查找元素   
count 返回匹配给定主键的元素的个数   
equal\_range 返回值匹配给定搜索值的元素组成的范围   
================Buckets======================   
bucket\_count 返回槽（Bucket）数   
max\_bucket\_count 返回最大槽数   
bucket\_size 返回槽大小   
bucket 返回元素所在槽的序号   
load\_factor 返回载入因子，即一个元素槽（Bucket）的最大元素数   
max\_load\_factor 返回或设置最大载入因子   
rehash 设置槽数   
reserve 请求改变容器容量

[70]: /images/20220523/bac5144b5df1470ba3d40897604bb259.png