LeetCode（1）：两数之和

写在前面：基本全部参考大神“Grandyang”的博客，附上网址：http://www.cnblogs.com/grandyang/p/4130379.html

写在这里，是为了做笔记，同时加深理解，希望有识之士一起加油。

Easy！

题目描述：

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

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

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

这道题给了我们一个数组，还有一个目标数target，让我们找到两个数字，使其和为target，乍一看就感觉可以用暴力搜索，但是猜到OJ肯定不会允许用暴力搜索这么简单的方法，于是去试了一下，果然是Time Limit Exceeded，这个算法的时间复杂度是O(n^2)。那么只能想个O(n)的算法来实现，由于暴力搜索的方法是遍历所有的两个数字的组合，然后算其和，这样虽然节省了空间，但是时间复杂度高。一般来说，我们为了提高时间的复杂度，需要用空间来换，这算是一个trade off吧，我们只想用线性的时间复杂度来解决问题，那么就是说只能遍历一个数字，那么另一个数字呢，我们可以事先将其存储起来，使用一个HashMap，来建立数字和其坐标位置之间的映射，我们都知道HashMap是常数级的查找效率，这样，我们在遍历数组的时候，用target减去遍历到的数字，就是另一个需要的数字了，直接在HashMap中查找其是否存在即可，注意要判断查找到的数字不是第一个数字，比如target是4，遍历到了一个2，那么另外一个2不能是之前那个2，整个实现步骤为：先遍历一遍数组，建立HashMap映射，然后再遍历一遍，开始查找，找到则记录index。

C++参考答案一：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> m;
        vector<int> res;
        for (int i = 0; i < nums.size(); ++i) {
            m[nums[i]] = i; //先遍历一遍数组，建立HashMap映射
        }
           //然后再遍历一遍，开始查找，找到则记录index
        for (int i = 0; i < nums.size(); ++i) {
            int t = target - nums[i];
            if (m.count(t) && m[t] != i) {//if里面的条件用于判断查找到的数字不是第一个数字
                res.push_back(i);
                res.push_back(m[t]);
                break;
            }
        }
        return res;
    }
};

或者可以写得更简洁一些，把两个for循环合并成一个（注意到答案一中两个for循环的循环条件是一模一样的）：

C++参考答案二：

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

解决思路：

第一个for循环把数组遍历一遍，建立map数据，第二个for循环进行查找，找到符合条件的则记录index。

知识点回顾：（注：下面知识点的页码标注，均依据《C++ primer plus》第六版）

容器（P695）

容器概念：容器是存储在其他对象的对象。被存储的对象必须是同一种类型的。不能将任何类型的对象存储在容器中，具体的说，类型必须是可赋值构造的和可赋值的。

vector（P195）

vector是C++众多容器类型中的一个，是一个十分有用的容器。是数组的一种类表示，它能够像容器一样存放各种类型的对象，简单地说，vector是一个能够存放多种类型的动态数组，能够增加和压缩数据。vector在C++标准模板库中的部分内容，它是一个多功能的，能够操作多种数据结构和算法的模板类和函数库。

使用vector需要注意以下几点：

1、如果你要表示的向量长度较长（需要为向量内部保存很多数），容易导致内存泄漏，而且效率会很低；

2、Vector作为函数的参数或者返回值时，需要注意它的写法：

 double Distance(vector<int>&a, vector<int>&b) 其中的“&”绝对不能少！！！

实例：vector<int>test;

//建立一个vector，int为数组元素的数据类型，test为动态数组名

简单的使用方法如下：

vector<int>test;//建立一个vector

test.push_back(1);

test.push_back(2);//把1和2压入vector，这样test[0]就是1，test[1]就是2。

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();

特别提示：这里有begin()与end()函数、front()与back()的差别

2、重要说明

vector的元素不仅仅可以是int,double,string,还可以是结构体，但是要注意：结构体要定义为全局的，否则会出错。

#include<stdio.h>  
#include<algorithm>  
#include<vector>  
#include<iostream>  
using namespace std;

typedef struct rect
{
    int id;
    int length;
    int width;

    //对于向量元素是结构体的，可在结构体内部定义比较函数，下面按照id,length,width升序排序。  
    bool operator< (const rect &a)  const
    {
        if (id != a.id)
            return id<a.id;
        else
        {
            if (length != a.length)
                return length<a.length;
            else
                return width<a.width;
        }
    }
}Rect;

int main()
{
    vector<Rect> vec;
    Rect rect;
    rect.id = 1;
    rect.length = 2;
    rect.width = 3;
    vec.push_back(rect);
    vector<Rect>::iterator it = vec.begin();
    cout << (*it).id << ' ' << (*it).length << ' ' << (*it).width << endl;
    
    return 0;
    cin.get();
    
}

3、算法

(1) 使用reverse将元素翻转：需要头文件#include<algorithm>

reverse(vec.begin(),vec.end());将元素翻转，即逆序排列！

(在vector中，如果一个函数中需要两个迭代器，一般后一个都不包含)

(2)使用sort排序：需要头文件#include<algorithm>，

sort(vec.begin(),vec.end());(默认是按升序排列,即从小到大).

可以通过重写排序比较函数按照降序比较，如下：

定义排序比较函数：

bool Comp(const int &a,const int &b)
{
    return a>b;
}
调用时:sort(vec.begin(),vec.end(),Comp)，这样就降序排序。 

输出Vector的中的元素   

vector<float> vecClass; 

int nSize = vecClass.size();   

 //打印vecClass,方法一：  

for(int i=0;i<nSize;i++)    
{    
   cout<<vecClass[i]<<"     ";    
}    
   cout<<endl;   

需要注意的是：以方法一进行输出时，数组的下标必须保证是整数。

 //打印vecClass,方法二：

for(int i=0;i<nSize;i++)    
{    
   cout<<vecClass.at(i)<<"     ";    
}    
   cout<<endl; 

//打印vecClass,方法三：输出某一指定的数值时不方便

for(vector<float>::iterator it = vecClass.begin();it!=vecClass.end();it++)    
{    
    cout<<*it<<"   ";    
}    
    cout<<endl; 

二维数组的使用：

#include "stdafx.h"  
#include <cv.h>  
#include <vector>   
#include <iostream>   
using namespace std;
int main()
{
    using namespace std;
    int out[3][2] = { 1, 2,
        3, 4,
        5, 6 };
    vector <int*> v1;

    v1.push_back(out[0]);
    v1.push_back(out[1]);
    v1.push_back(out[2]);

    cout << v1[0][0] << endl;//1  
    cout << v1[0][1] << endl;//2  
    cout << v1[1][0] << endl;//3  
    cout << v1[1][1] << endl;//4  
    cout << v1[2][0] << endl;//5  
    cout << v1[2][1] << endl;//6  

    return 0;
}

vector中insert()的用法详解

insert() 函数有以下三种用法: 
1、在指定位置loc前插入值为val的元素,返回指向这个元素的迭代器
2、在指定位置loc前插入num个值为val的元素 

3、在指定位置loc前插入区间[start, end)的所有元素 

//创建一个vector,置入字母表的前十个字符   
vector <char> Avector;   
for( int i=0; i < 10; i++ )   
  Avector.push_back( i + 65 );   
  
  
//插入四个C到vector中   
vector <char>::iterator theIterator = Avector.begin();   
Avector.insert( theIterator, 4, 'C' );   
  
  
//显示vector的内容   
for( theIterator = Avector.begin(); theIterator != Avector.end(); theIterator++ )   
  cout < < *theIterator;   

这段代码需要再完善方可运行，运行结果将显示:CCCCABCDEFGHIJ

unordered_map的定义

详见原网页：http://www.cplusplus.com/reference/unordered_map/unordered_map/

template < class Key,
class T,
class Hash = hash<Key>,
class Pred = equal_to<Key>,
class Alloc = allocator< pair<const Key,T> >> class unordered_map;

模版参数说明：

Key 
主键的类型。 
在类模板内部，使用其别名为 key_type 的成员类型。 
T 
被映射的值的类型。 
在类模板内部，使用其别名为 mapped_type 的成员类型。 
Hash 
一元谓词，以一个 Key 类型的对象为参数，返回一个基于该对象的 size_t 类型的唯一值。可以是函数指针（Function pointer）类型或函数对象（Function object）类型。在类模板内部，使用其别名为 hasher 的成员类型。 
Pred 
二元谓词，以两个 Key 类型的对象为参数，返回一个 bool 值，如果第一个参数等价于第二个参数，该 bool 值为 true，否则为 false。默认为 std::equal_to.可以是函数指针类型（Function pointer）类型或函数对象（Function object）类型.在类模板内部，使用其别名为 key_equal 的成员类型。 
Alloc 
容器内部用来管理内存分配及释放的内存分配器的类型。这个参数是可选的，它的默认值是 std::allocator，这个是一个最简单的非值依赖的（Value-independent）内存分配器。在类模板内部，使用其别名为 allocator_type 的成员类型。  

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 请求改变容器容量

测试代码：

#include <unordered_map>
#include <iostream>
#include <string>

using namespace std;

void PrintIntDoubleUnOrderedMap(unordered_map<int, double>& m, char* pre)
{
    unordered_map<int, double>::iterator iter;
    cout << pre;
    for (iter = m.begin(); iter != m.end(); ++iter)
        cout << "(" << iter->first << ", " << iter->second << ")" << " ";
    cout << endl;
}

void UnOrderedMapExp1()
{
    unordered_map<int, double> m;
    //没有key,就自动创建
    m[0] = 1.11;
    //普通插入，使用类型转换
    m.insert(unordered_map<int, double>::value_type(1, 2.22));
    //带暗示的插入，pair<int, double>就相当于上面的unordered_map<int ,double>
    m.insert(m.end(), pair<int, double>(2, 3.33));
    PrintIntDoubleUnOrderedMap(m, "插入元素之前的m:");

    //插入一个范围
    unordered_map<int, double> m2;
    m2.insert(unordered_map<int, double>::value_type(3, 4.44));
    m2.insert(unordered_map<int, double>::value_type(4, 5.44));
    m2.insert(unordered_map<int, double>::value_type(5, 6.44));
    m.insert(m2.begin(), m2.end());

    m.emplace(6, 5.55);
    m.emplace_hint(m.end(), 7, 3.09);
    m.at(5) = 3.333333;

    PrintIntDoubleUnOrderedMap(m, "插入元素之后m：");

    unordered_map<int, double>::iterator iter;
    iter = m.find(4);
    if (iter != m.end())
    {
        cout << "m.find(4): ";
        cout << "(" << iter->first << ", " << iter->second << ")" << endl;
    }

    if (iter != m.end())
    {
        m.erase(iter);
    }
    PrintIntDoubleUnOrderedMap(m, "删除主键为4的元素之后m:");

    //遍历删除
    for (iter = m.begin(); iter != m.end(); ++iter)
    {
        if (iter->first == 2)
        {
            m.erase(iter);
            break;
        }
    }

    //内部数据
    cout << "bucket_count:" << m.bucket_count() << endl;
    cout << "max_bucket_count:" << m.max_bucket_count() << endl;
    cout << "bucket_size:" << m.bucket_size(0) << endl;
    std::cout << "load_factor：" << m.load_factor() << std::endl;
    std::cout << "max_load_factor：" << m.max_load_factor() << std::endl;
    PrintIntDoubleUnOrderedMap(m, "删除主键为2的元素后的foo1：");
    m.clear();
    PrintIntDoubleUnOrderedMap(m, "清空后的foo1：");
}

int main()
{
    UnOrderedMapExp1();

    return 0;
}

以类作为key,value

只是用STL提供的基本类型int, char, long等和stringz作为key，value,STL提供了哈希函数和比较函数。但是用自己定义的类时，需要自己定义哈希函数和比较函数

//hash函数
template <typename T>  
class hash  
{  
    public:  
        size_t operator()(const T& o) const { return 0; }  
};  

//compare函数
template <typename T>  
class equal_to  
{  
  public:  
    bool operator()(const T& a, const T& b) const { return a == b; }  
};  

下面以一个学号姓名为例子来实现

#include <unordered_map>
#include <iostream>
#include <string>

using namespace std;

//自己设计类，作为key和value


//学号
class Number
{
    string str;
public:
    Number() { }
    Number(string s) { str = s; }

    const string& get() const
    {
        return str;
    }
};

//姓名
class Name 
{
    string str;
public:
    Name() {}
    Name(string s) { str = s; }

    const string& get() const
    {
        return str;
    }
};


//哈希函数对象实现
// 必须为const
class MyHash 
{
public:

    size_t operator()(const Number& num) const
    {
        hash<string> sh;        //使用STL中hash<string>
        return sh(num.get());
    }
};

//实现equal_to对象
//必须为const
class MyEqualTo {
public:

    bool operator()(const Number& n1, const Number& n2) const
    {
        return n1.get() == n2.get();
    }
};

int main()
{
    unordered_map<Number, Name, MyHash, MyEqualTo> map;
    map.emplace(Number("1000"), Name("A"));
    map.emplace(Number("1001"), Name("G"));
    map.emplace(Number("1002"), Name("E"));
    map.emplace(Number("1003"), Name("D"));


    unordered_map<Number, Name, MyHash, MyEqualTo>::iterator iter;
    Number num("1001");
    iter = map.find(num);

    if (iter != map.end())
        cout << "Number: " << iter->first.get() << "," << "Name： " << iter->second.get() << endl;

    else
        cout << "Not found!" << endl;

    return 0;
}

官方解答：

方法一：暴力法

暴力法很简单。遍历每个元素x，并查找是否存在一个值与target-x相等的目标元素。Java代码：

public int[] twoSum(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[j] == target - nums[i]) {
                return new int[] { i, j };
            }
        }
    }
    throw new IllegalArgumentException("No two sum solution");
}

复杂度分析：

• 时间复杂度：O(n²)， 对于每个元素，我们试图通过遍历数组的其余部分来寻找它所对应的目标元素，这将耗费O(n) 的时间。因此时间复杂度为 O(n​^2​​)。

• 空间复杂度：O(1)。

方法二：两遍哈希表

为了对运行时间复杂度进行优化，我们需要一种更有效的方法来检查数组中是否存在目标元素。如果存在，我们需要找出它的索引。保持数组中的每个元素与其索引相互对应的最好方法是什么？哈希表。

通过以空间换取速度的方式，我们可以将查找时间从 O(n)O(n) 降低到 O(1)O(1)。哈希表正是为此目的而构建的，它支持以 近似 恒定的时间进行快速查找。我用“近似”来描述，是因为一旦出现冲突，查找用时可能会退化到 O(n)O(n)。但只要你仔细地挑选哈希函数，在哈希表中进行查找的用时应当被摊销为 O(1)O(1)。

一个简单的实现使用了两次迭代。在第一次迭代中，我们将每个元素的值和它的索引添加到表中。然后，在第二次迭代中，我们将检查每个元素所对应的目标元素（target - nums[i]target−nums[i]）是否存在于表中。注意，该目标元素不能是 nums[i]nums[i] 本身！

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        map.put(nums[i], i);
    }
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement) && map.get(complement) != i) {
            return new int[] { i, map.get(complement) };
        }
    }
    throw new IllegalArgumentException("No two sum solution");
}

复杂度分析：

• 时间复杂度：O(n)， 我们把包含有 n 个元素的列表遍历两次。由于哈希表将查找时间缩短到 O(1) ，所以时间复杂度为 O(n)。

• 空间复杂度：O(n)， 所需的额外空间取决于哈希表中存储的元素数量，该表中存储了 n 个元素。

方法三：一遍哈希表

事实证明，我们可以一次完成。在进行迭代并将元素插入到表中的同时，我们还会回过头来检查表中是否已经存在当前元素所对应的目标元素。如果它存在，那我们已经找到了对应解，并立即将其返回。

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement)) {
            return new int[] { map.get(complement), i };
        }
        map.put(nums[i], i);
    }
    throw new IllegalArgumentException("No two sum solution");
}

复杂度分析：

• 时间复杂度：O(n)， 我们只遍历了包含有 n个元素的列表一次。在表中进行的每次查找只花费 O(1)的时间。

• 空间复杂度：O(n)， 所需的额外空间取决于哈希表中存储的元素数量，该表最多需要存储 n 个元素。