刚开始刷leetcode，总结一下来备忘

第一道题，也不是很难，题目如下：

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.

For example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

这道题的题目意思从给的例子中也很容易看出来，就是给了一个数组nums，和一个目标值target，返回nums中的两个相加等于target的元素的下标数组，首先在最后提交的测试用例中，nums这个数组中的元素不一定是和例子一样按照从小到大的顺序排列的，其次在题目中已经假设了每一组input都有且仅有一组解，这样也就不用考虑没有或者有多组解的情况，明确了这两点，一下可以想到的就是一个复杂度是O(n^2)的解法，下面提供了C++和javascript两种写法。

1）C++写法

 1 class Solution {
 2 public:
 3     vector<int> twoSum(vector<int>& nums, int target) {
 4         for(int i=0;i<nums.size();i++){
 5             for(int j=i+1;j<nums.size();j++){
 6                 if(nums[i]+nums[j]==target){
 7                     vector<int> result(2);
 8                     result[0]=i;
 9                     result[1]=j;
10                     return result;
11                 }
12             }
13         }
14     }
15 };

2）javascript写法

1 var twoSum = function(nums, target) {
2     for(var i=0;i<nums.length;i++){
3         for(var j=i+1;j<nums.length;j++){
4             if(nums[i]+nums[j]==target){
5                 return [i,j];
6             }
7         }
8     } 
9 };

这两种方法提交也都通过了，不过肯定不是最优解，看到别人的最优解法的复杂度是O(n)，使用哈希表存储nums数组和target之间的差距，在访问nums数组的时候都首先查找当前访问的数组元素是不是和hash_table中的某一个键相等，若不相等，则把该差距作为hash_table的键，把当前访问元素的下标作为对应的值，存在hash_table中，若相等，取出该键对应的值和当前访问的下标一起返回即可。

1）在C++中实现hash_table我是用了map类库实现，代码如下：

 1 class Solution {
 2 public:
 3     vector<int> twoSum(vector<int>& nums, int target) {
 4         vector<int> result;
 5         map<int,int> map_container;
 6         for(int i=0;i<nums.size();i++){
 7             map<int,int>::iterator it=map_container.find(nums[i]);
 8             if(it == map_container.end()){
 9                 map_container[target-nums[i]]=i;
10             }
11             else{
12                 result.push_back(it->second);
13                 result.push_back(i);
14                 return result;
15             }
16         }
17     }
18 };

2）在javascript中直接使用object构造键值对实现hash_table即可，代码如下：

 1 var twoSum = function(nums, target) {
 2     var map_container={};
 3     for(var i=0;i<nums.length;i++){
 4         if(nums[i] in map_container){
 5             return [map_container[nums[i]],i];
 6         }
 7         else{
 8             map_container[target-nums[i]]=i;
 9         }
10     }
12 };

总结使用到的有关C++的知识点：

1）关于vector

初始化：vector<type> a(init_size)    type:表示vector中的元素类型，init_size也可以省略，如果显示则表示初始化vector的大小

动态增加元素：使用方法push_back()，即在原来的vector末尾附加新元素。

遍历vector：两种方法都可以，使用size()方法返回vector的大小然后用下标访问的方法即可，或者使用遍历器遍历vector<type>::iterator it，it的本质是一个指针，所以(*it)就表示当前it指针所指vector位置的元素的值，当然上面那道题适合的方法是下标访问的方法。

2）关于map

初始化：map<key_type,value_type> map_container  key_type:表示map中的键的元素的类型，value_type:表示map中的值的元素类型。

插入键值对：直接用map_container[key]=value的形式插入即可

判断一个键是否存在：使用find()和遍历器实现，find()函数找到要查找的键返回该键所在的位置指针，没找到返回end()，所以只需要判断是否是最后一个迭代器就知道是否存在查找的键。

访问某一个键值对：使用map_container[key]得到对应的value，或者使用map<type,type>::iterator it遍历器，it作为指针支持，it->first返回键，it->second返回值。

总结javascript中用到的知识点：

主要就是使用object键值对来构造哈希表：

1）使用对象初始化，map_container={}

添加新的键值对直接使用点操作符，或者当键可能引起操作错误的时候使用方括号来插入，如map_container[key]=value,map_container.key=value

判断一个键是否能存在：使用key in map_container，返回true表示存在，否则返回false。

2）强调注意

访问对象属性的方法有两个，一个是使用点操作符一个是使用方括号来访问，这两个方法在大多数情况下没有什么差别，但是如果访问的属性是一个变量的时候，则应该使用方括号来访问，还有就是一些属性名中包含会导致语法错误的字符，或者属性名使用的是关键字或保留字，这时候也要使用方括号来访问，使用点操作符会导致语法错误，总结来说就是键是数字，或者带有空格，或者把键的值赋给一个变量来访问的时候，就应该使用方括号来访问。

Two Sum