Leetcode DAY2 两数之和_it != hashtable.end()

一、问题描述

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

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

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

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

二、问题分析

2.1 遍历求解

根据题意，对于给定一个数x，判断是否存在target-x，比较容易想到的办法是遍历整个数组，并且因为不能重复出现元素，所以只需要判断x之后的数是否满足要求即可。代码如下：

class Solution {
public:
//知识点1：vector的概念与性质
    vector<int> twoSum(vector<int>& nums, int target) {
        int n = nums.size();
//知识点2：i++和++i的区别
        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 {};
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

该算法的时间复杂度为O(n²)，空间复杂度为O(1)。

2.2 哈希表

可以看出，遍历求解中时间复杂度较高，可以从这一方面优化，也就是简化查值过程。因此，可以采用建立哈希表的方式，对于单个未知数x，利用哈希表寻找target-x的时间复杂度可以降为O(1)，对于含有N个数的数组，整个算法的时间复杂度为O(N)；由于存储哈希表，空间复杂度为O(N)。代码如下：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
//知识点3：哈希表
//建立哈希表
        unordered_map<int,int>hashtable;
        for(int i = 0;i < nums.size();++i)
        {
//知识点4：auto标识符
//知识点5：迭代器iterator的概念与性质
//针对该数nums[i]，在哈希表内查值。数组下标i为值，nums[i]数本身为键值。
           auto it = hashtable.find(target - nums[i]);
//若在已有哈希表内查到值则返回对应下标。因为是与该数前面的数进行匹配，因此该数下标i返回时在后面。
           if(it != hashtable.end())
           return {it->second,i};
//将该数nums[i]加入哈希表
           hashtable[nums[i]] = i;
         }
         return {};
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

三、知识点拓展

知识点1：vector的概念与性质

vector是顺序容器，本质是动态数组。创建vector容器时需要说明该容器内元素的类型。如下：

vector<int> twoSum;
1

vector容器在做形参传递时，可以采用以下三种方式：

void init_vector1(vector<int>vectest);
void init_vector2(vector<int>&vectest);
void init_vector3(vector<int>*vectest);
1
2
3

init_vector1中是值传递，形参的改变不会对实参有影响，并且会调用vector的拷贝构造函数将实参的值复制给形参。

init_vector2和init_vector3分别是引用传递和指针传递，它们会对实参做出影响。

建议在实际应用中采用引用传递，如下文所示。

vector<int> twoSum(vector<int>& nums, int target);
1

参考文献：
[1]Vector容器
[2]c++中vector做形参传递的问题

知识点2：i++和++i的区别

1、赋值顺序不同

i++先赋值后运算，++i先运算后赋值。

2、效率不同

++i的效率比i++高。因为i++先赋值后运算，因此要多生成一个局部对象。如下所示。

CDemo CDemo::operator++ ()
{  //前置++
    ++n;
    return *this;
}
CDemo CDemo::operator ++(int k)
{  //后置++
    CDemo tmp(*this);  //记录修改前的对象
    n++;
    return tmp;  //返回修改前的对象
}
1
2
3
4
5
6
7
8
9
10
11

3、i++无法做左值，++i可以

左值是对应内存中有确定存储地址的对象的表达式的值，而右值是所有不是左值的表达式的值。一般来说，左值是可以放到赋值符号左边的变量。

但能否被赋值不是区分左值与右值的依据。比如，C++的const左值是不可赋值的；而作为临时对象的右值可能允许被赋值。左值与右值的根本区别在于是否允许取地址&运算符获得对应的内存地址。

参考文献：i++与++i的区别

知识点3：哈希表

哈希表是一个采用键值和值相互对应的函数，在c++中，与哈希表对应的容器是unordered_map（无序容器）。因此采用unordered_map建立哈希表。

unordered_map<int,int>hashtable;
1

该句建立一个名为hashtable的，键值对为<int,int>类型的unordered_map容器。其中<int,int>是指键值对类型，前者是键的类型，后者是值的类型。

auto it = hashtable.find(target - nums[i]);
1

find(key)是unordered_map容器中寻找键key对应的值的成员方法。若键key与其值的键值对在容器中存在，则返回一个指向该键值对的正向迭代器，反之则返回一个指向容器中最后一个键值对之后位置的迭代器。

if(it != hashtable.end())
1

该句判断是否存在我们需要的键值对。成员方法end()生成指向容器中最后一个键值对之后位置的迭代器。

参考文献：unordered_map容器

知识点4：auto标识符

1、auto就是根据变量值推断变量类型。
2、使用auto时必须初始化变量。
3、auto是一个占位符，并不是一个类型，因此无法进行类型转换之类的操作。

参考文献：auto标识符

知识点5：迭代器iterator的概念与性质

访问、读写容器中的元素，需要使用迭代器iterator。容器可以看作为吉他，迭代器可以看作为拨片，吉他（容器）是声音（元素）的载体，但是使吉他发出声音（能够访问到容器的元素）需要使用拨片（迭代器）。

迭代器根据访问方式分为正向迭代器、双向迭代器、随机访问迭代器。不同的访问方式使得迭代器可以做的运算不同。

迭代器常用功能：
1、定义一个正向迭代器
容器类名::iterator 迭代器名;

vector<int>::iterator i; 
1

2、取得迭代器所指元素

a = *i;
1

3、移动迭代器，访问下一个元素（移动方法视迭代器类别变化）

++i;
1

在unordered_map容器中，迭代器指向键值对，即指向两个元素，键和值。因此通过迭代器访问unordered_map容器时，需要说明访问的是哪个元素。其中first是键，second是值。

return {it->second,i};
1

上句即为访问键值对中的值。

参考文献：迭代器