1.两数之和

一.题目描述

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

二.思路分析

方法1：

直接暴力枚举出所有可能的情况，但是时间复杂度较大；

方法2：

可以使用哈希表，将数组中的元素放入哈希表中，这样，查找一个元素的时间复杂度为1，极大地提高了效率；

三.解题代码

解法一：（C语言，暴力枚举）

#include

int* twoSum(int* nums, int numsSize, int target) 
{
	int* ret = malloc(sizeof(int) * 2);
	for (int i = 0; i < numsSize; ++i) {
		for (int j = i + 1; j < numsSize; ++j) {
			if (nums[i] + nums[j] == target)
			{				
				ret[0] = i;
				ret[1] = j;
			}
		}
	}
	return ret;
}

int main()
{
	int nums[] = { 2,3,5,7,9 };
	int numsSize = sizeof(nums)/sizeof(nums[0]);
	int target = 10;
	int* p = twoSum(nums,numsSize,target);
	printf("%d\n" , *p);
	printf("%d\n", *++p);
	return 0;
}

解法二：（C++，使用STL，暴力枚举）

#include
using namespace std;
#include

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (nums[i] + nums[j] == target) {
                    return { i, j };
                }
            }
        }
        return {};
    }
};

int main()
{
    vector<int> nums= { 2,3,4,5,6 };
    vector<int> ret;
    Solution So;
    int target = 11;
    ret = So.twoSum(nums, target);
    cout << ret[0] << ret[1] << endl;
    return 0;
}

解法三：（哈希表）

#include
using namespace std;
#include
#include

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hashtable;
        for (int i = 0; i < nums.size(); ++i) {
            auto it = hashtable.find(target - nums[i]);
            if (it != hashtable.end()) {
                return { it->second, i };
            }
            hashtable[nums[i]] = i;
        }
        return {};
    }
};

int main()
{
    Solution So;
    int target=11;
    vector<int> ret;
    vector<int> nums= { 2,3,4,5,6 };
    ret = So.twoSum(nums, target);
    cout << ret[0] << ret[1] << endl;
    return 0;
}

四.get新知识

1. 数组作为参数时，在函数中对数组元素的修改就等同于对原数组元素的修改。

2. new分配的对象，不管单个对象还是多个对象的分配，都是默认初始化。但可以对数组进行值初始化，方法就是：在大小之后添加一对空括号。

   int *p1 = new int[10];    // 10个未初始化int
   int *p2 = new int[10](); // 10个值初始化为0的int
   

   int *p2 = new int[10]();申请了空间，而且进行了初始化int *p1 = new int[10];只申请空间，没有进行初始化原因：对于一些结构体，我们可以看到（）往往表示构造函数，int是基本类型算初始化吧理由：你可以测试输出两种的值你会发现p1的值未知，而p2清零了

   new运算符只是申请分配一个内存空间而已，因为不知道为其分配对象的名称，所以分配之后返回的只是一个指向该对象的指针，并没有初始化，加上一个（）后，就相当于调用了默认构造函数，会默认初始化，用0来初始化；

3. 函数返回值为一个数组时，应该用一个指针来接收，要输出接收的数组中的每个值时，令指针依次增加遍历该数组即可；

4. vector赋值 *** 作：

   ①定义具有10个整型元素的向量（尖括号为元素类型名，它可以是任何合法的数据类型），不具有初值，其值不确定

   vectora(10);

   ②定义具有10个整型元素的向量，且给出的每个元素初值为1
   vectora(10,1);

   ③用向量b给向量a赋值，a的值完全等价于b的值
   vectora(b);

   ④将向量b中从0-2（共三个）的元素赋值给a，a的类型为int型
   vectora(b.begin(),b.begin+3);

   ⑤ 从数组中获得初值
   int b[7]={1,2,3,4,5,6,7}; vector a(b,b+7）;

   ⑥先定义一个容器arr，然后可以使用vector中的内置函数；

   ​ vector arr; ​ arr = { 2,3,4,5,6 }; ​ vector nums(arr.begin(), arr.end());

5. unordered_map

   • unordered_map是一个将key和value关联起来的容器，它可以高效的根据单个key值查找对应的value。
   • key值应该是唯一的，key和value的数据类型可以不相同。
   • unordered_map存储元素时是没有顺序的，只是根据key的哈希值，将元素存在指定位置，所以根据key查找单个value时非常高效，平均可以在常数时间内完成。
   • unordered_map查询单个key的时候效率比map高，但是要查询某一范围内的key值时比map效率低。
   • 可以使用[] *** 作符来访问key值对应的value值。

   //定义哈希表
   unordered_map<key,value> Map_name;
   
   //插入元素
   ①Map[key]=value;
   ②Map_name.insert(pair<int,int>(key,value));
   ③unordered_map<int,int>Map_name={{key1,value1},{key2,value2}};
   
   //查找键值 
   Map_name.find(key);
   
   unomap.emplace(key, value);//使用变量方式，插入一个元素
   unomap.emplace("456", 7);//也可以直接写上key和value的值
   
   //根据key删除,如果没找到n=0
   auto n = Map_name.erase("test")   //删除
   
       
   //改
   auto it = umap.find(key); 
   if(it != umap.end()) 
       it->second = new_value; 
   
   //遍历整个map，输出key及其对应的value值
   //使用find彻底找到这个数值，然后在进行改，可以保证作用域是整个程序。
   for(auto x:unomap)
   {
   	auto it = umap.find(key) //改
   	if(it != umap.end()) 
   	    it->second = new_value; 
   }	
      
   //遍历整个map，输出key及其对应的value值
   for (auto x : Map_name)
       cout << x.first << "  " << x.second << endl;
   
   //遍历整个map，并根据其key值，查看对应的value值
   for (auto x : Map_name)
       cout << Map_name[x.first] << endl;
   
   // 遍历
   map<string, int>::iterator iter;  //定义一个迭代器iter
   for(iter=dict.begin();iter!=dict.end();iter++)
       cout<<iter->first<<ends<<iter->second<<endl;
   

   c++中map与unordered_map的区别
   • 运行效率方面：unordered_map最高，而map效率较低但 提供了稳定效率和有序的序列。
   • 占用内存方面：map内存占用略低，unordered_map内存占用略高,而且是线性成比例的。
   头文件
   • map: #include < map >
   • unordered_map: #include < unordered_map >
   内部实现机理

   map： map内部实现了一个红黑树，该结构具有自动排序的功能，因此map内部的所有元素都是有序的，红黑树的每一个节点都代表着map的一个元素，因此，对于map进行的查找，删除，添加等一系列的 *** 作都相当于是对红黑树进行这样的 *** 作，故红黑树的效率决定了map的效率。
   unordered_map: unordered_map内部实现了一个哈希表，因此其元素的排列顺序是杂乱的，无序的；

   优点、缺点、使用场景

   map
   优点：有序性，这是map结构最大的优点，其元素的有序性在很多应用中都会简化很多的 *** 作。红黑树，内部实现一个红黑书使得map的很多 *** 作在lgn的时间复杂度下就可以实现，因此效率非常的高。
   缺点：空间占用率高，因为map内部实现了红黑树，虽然提高了运行效率，但是因为每一个节点都需要额外保存父节点，孩子节点以及红/黑性质，使得每一个节点都占用大量的空间
   适用处：对于那些有顺序要求的问题，用map会更高效一些。

   unordered_map
   优点：内部实现了哈希表，因此其查找速度是常量级别的。
   缺点：哈希表的建立比较耗费时间
   适用处：对于查找问题，unordered_map会更加高效一些，因此遇到查找问题，常会考虑一下unordered_map

6. auto

   一、用途

   auto是c++程序设计语言的关键字。用于两种情况

   （1）声明变量时根据初始化表达式自动推断该变量的类型

   （2）声明函数时函数返回值的占位符

   二、简要理解

   auto可以在声明变量时根据变量初始值的类型自动为此变量选择匹配的类型。

   举例：对于值x=1；既可以声明： int x=1 或 long x=1，也可以直接声明 auto x=1

   三、用法

   根据初始化表达式自动推断被声明的变量的类型，如：

   auto f = 3.14;  //double
   auto s("hello");  //const char*
   auto z = new auto(9);  //int *
   auto x1 = 5, x2 = 5.0, x3 = 'r';   //错误，必须是初始化为同一类型
   

   但是，这么简单的变量声明类型，不建议用auto关键字，而是应更清晰地直接写出其类型。

   auto关键字更适用于类型冗长复杂、变量使用范围专一时，使程序更清晰易读。如：

   std::vector<int> vect; 
    for(auto it = vect.begin(); it != vect.end(); ++it)
    {  //it的类型是std::vector::iterator
       std::cin >> *it;
     }
   

   使用std::vectorstd::string::iterator来定义i是C++常用的良好的习惯，但是这样长的声明带来了代码可读性的困难，因此引入auto，使代码可读性增加。并且使用STL将会变得更加容易;