【leetcode刷题1 1-两数之和（stl中map容器的学习）】

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

• 一、两数之和
• 二、使用步骤
• • 1.错误代码
  • 2.最终结果
  • 3.题解学习
  • • 3.1stl中的map容器
    • • 3.1.1插入元素
      • 3.1.2查找元素
      • 3.1.3删除元素
      • 3.1.4 map大小
      • 3.1.5基本函数

给定一个整数数组 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]

提示：

2 <= nums.length <= 10⁴
-10⁹ <= nums[i] <= 10⁹
-10⁹ <= target <= 10⁹
只会存在一个有效答案

代码1如下（示例）：

class Solution {
public:
    vector twoSum(vector& nums, int target) {
        int begin,end;
        for(int i =0;i
            for(int j =i;j
                if(nums[i]+nums[j]== target){
                    begin = i;
                    end = j;
                }
            }
        }
        vector vec;
        vec.push_back(begin);
        vec.push_back(end);
        return vec;
    }

};

执行结果：错误。在类似[3,3] 6这种情况下期望结果应该是[0,1]，程序结果是[0].遍历过程有问题。

代码如下（示例）：

class Solution {
public:
    vector twoSum(vector& nums, int target) {
        int begin,end;
        for(int i =0;i
            for(int j =i+1;j
                if(nums[i]+nums[j]== target){
                    begin = i;
                    end = j;
                }
            }
        }
        vector vec;
        vec.push_back(begin);
        vec.push_back(end);
        return vec;
    }

};

时间复杂度为O（n）的算法

class Solution {
public:
    vector twoSum(vector& nums, int target) {
        unordered_maphashtable;
        for(int i = 0;i < nums.size();++i)
        {
//针对该数nums[i]，在哈希表内查值。数组下标i为值，nums[i]数本身为键值。
           auto it = hashtable.find(target - nums[i]);
//如果找到目标值，则返回
           if(it != hashtable.end())
           return {it->second,i};
//否则将该数nums[i]加入哈希表
           hashtable[nums[i]] = i;
         }
         return {};
    }
};

①for循环中,for(int i = 0;i < 6;i++)和for(int i = 0;i < 6;++i)效果一样
② while(i++)是先用i的初始化值做循环变量再i+1
而while(++i)是先用i的初始值+1,再循环

map是STL的一个关联容器，以键值对存储的数据，其类型可以自己定义，每个关键字在map中只能出现一次，关键字不能修改，值可以修改；map同set、multiset、multimap（与map的差别仅在于multimap允许一个键对应多个值）内部数据结构都是红黑树，而java中的hashmap是以hash table实现的。所以map内部有序（自动排序，单词时按照字母序排序），查找时间复杂度为O(logn).

// 定义一个map对象
map mapStudent;
 
// 第一种 用insert函數插入pair
mapStudent.insert(pair(000, "student_zero"));
 
// 第二种 用insert函数插入value_type数据
mapStudent.insert(map::value_type(001, "student_one"));
 
// 第三种 用"array"方式插入
mapStudent[123] = "student_first";
mapStudent[456] = "student_second"

这三种方法的区别在于，用insert方法时，如果对应关键字在表中已经有对应的值，操作则会失败。

// find 返回迭代器指向当前查找元素的位置否则返回map::end()位置
iter = mapStudent.find("123");
 
if(iter != mapStudent.end())
       cout<<"Find, the value is"<second< 
3.1.3删除元素 
//迭代器刪除
iter = mapStudent.find("123");
mapStudent.erase(iter);
 
//用关键字刪除
int n = mapStudent.erase("123"); //如果刪除了會返回1，否則返回0
 
//用迭代器范围刪除 : 把整个map清空
mapStudent.erase(mapStudent.begin(), mapStudent.end());
//等同于mapStudent.clear()

 
3.1.4 map大小 
int nSize = mapStudent.size();
 
3.1.5基本函数 
C++ maps是一种关联式容器，包含“关键字/值”对
 
 begin()         返回指向map头部的迭代器

 clear(）        删除所有元素

 count()         返回指定元素出现的次数, (帮助评论区理解： 因为key值不会重复，所以只能是1 or 0)

 empty()         如果map为空则返回true

 end()           返回指向map末尾的迭代器

 equal_range()   返回特殊条目的迭代器对

 erase()         删除一个元素

 find()          查找一个元素

 get_allocator() 返回map的配置器

 insert()        插入元素

 key_comp()      返回比较元素key的函数

 lower_bound()   返回键值>=给定元素的第一个位置

 max_size()      返回可以容纳的最大元素个数

 rbegin()        返回一个指向map尾部的逆向迭代器

 rend()          返回一个指向map头部的逆向迭代器

 size()          返回map中元素的个数

 swap()           交换两个map

 upper_bound()    返回键值>给定元素的第一个位置

 value_comp()     返回比较元素value的函数