LeetCode——1. Two Sum

一、问题描述

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example1:

Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

二、解题思路

给定一个数组,和一个目标数target,要求数组中,和为target的两个数的下标。
想到的方法是暴力求法,即直接逐个遍历数组,找出满足要求的两个数。尽管这种方法能成功AC,但显然效率不高,这种方法比较耗时。需要寻找更加优化的算法。
查阅资料和题解思路得知,更加优化的方法是使用哈希表,这是一种通过以空间换取速度的方式,我们可以将查找时间从 O(n)降低到 O(1)。主要有以下两种:

1.两遍哈希表
一个简单的实现使用了两次迭代。在第一次迭代中,我们将每个元素的值和它的索引添加到表中。然后,在第二次迭代中,我们将检查每个元素所对应的目标元素(target - nums[i])是否存在于表中。

2.一遍哈希表
更优化的方法是,我们可以一次完成计算。在进行迭代并将元素插入到表中的同时,我们还会回过头来检查表中是否已经存在当前元素所对应的目标元素。如果它存在,那我们已经找到了对应解,并立即将其返回。

这里将这两种方法都实现了一遍。

三、代码

  1. 解法1 暴力求法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    class {
    public:
    vector<int> twoSum(vector<int>& nums, int target) {
    vector<int> indices;
    for(int i=0;i<nums.size()-1;i++)
    {
    indices.push_back(i);
    for(int j=i+1;j<nums.size();j++)
    {
    if(nums[j]==target-nums[i])
    {
    indices.push_back(j);
    return indices;
    }
    }
    indices.pop_back();
    }
    return indices;
    }
    };
  2. 解法2 两遍哈希表

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    class {
    public:
    vector<int> twoSum(vector<int>& nums, int target) {
    map<int,int> hash;
    vector<int> indices;
    for(int i = 0; i < nums.size(); i++)
    {
    hash[nums[i]]=i;
    }
    for (int i = 0; i < nums.size(); i++)
    {
    int complement = target - nums[i];
    if (hash.count(complement) && hash[complement] != i)
    {
    indices.push_back(i);
    indices.push_back(hash[complement]);
    break;
    }
    }
    return indices;
    }
    };
  3. 一遍哈希表

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    class {
    public:
    vector<int> twoSum(vector<int>& nums, int target) {
    map<int,int> hash;
    vector<int> indices;
    for (int i = 0; i < nums.size(); i++)
    {
    int complement = target - nums[i];
    if (hash.count(complement))
    {
    indices.push_back(i);
    indices.push_back(hash[complement]);
    break;
    }
    hash[nums[i]]=i;
    }
    return indices;
    }
    };

更新:map与unordered_map区别
原文:https://blog.csdn.net/BillCYJ/article/details/78985895
1.内部实现机理不同
map: map内部实现了一个红黑树(红黑树是非严格平衡二叉搜索树,而AVL是严格平衡二叉搜索树),红黑树具有自动排序的功能,因此map内部的所有元素都是有序的,红黑树的每一个节点都代表着map的一个元素。

unordered_map: unordered_map内部实现了一个哈希表(也叫散列表,通过把关键码值映射到Hash表中一个位置来访问记录,查找的时间复杂度可达到O(1),其在海量数据处理中有着广泛应用)。因此,其元素的排列顺序是无序的。

2.优缺点以及适用处
map:
优点:

  1. 有序性,这是map结构最大的优点,其元素的有序性在很多应用中都会简化很多的操作
  2. 红黑树,内部实现一个红黑书使得map的很多操作在lgn的时间复杂度下就可以实现,因此效率非常的高

缺点:
空间占用率高,因为map内部实现了红黑树,虽然提高了运行效率,但是因为每一个节点都需要额外保存父节点、孩子节点和红/黑性质,使得每一个节点都占用大量的空间

适用处:对于那些有顺序要求的问题,用map会更高效一些

unordered_map:
优点: 因为内部实现了哈希表,因此其查找速度非常的快

缺点: 哈希表的建立比较耗费时间

适用处:对于查找问题,unordered_map会更加高效一些,因此遇到查找问题,常会考虑一下用unordered_map

总结:

  1. 内存占有率的问题就转化成红黑树 VS hash表 , 还是unorder_map占用的内存要高。
  2. 但是unordered_map执行效率要比map高很多
  3. 对于unordered_map或unordered_set容器,其遍历顺序与创建该容器时输入的顺序不一定相同,因为遍历是按照哈希表从前往后依次遍历的