1，第一道算法题，题目如下：
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.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
翻译一下就是：给你一个整型数组，需要你返回两个数，这两个数相加等于一个指定的数。
你必须保证每一个输入的数组都有且只有一个确定的解。
解题过程：首先是最笨的方法，两层嵌套的for循环遍历，将所有组合测试一遍，代码比较简单。
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[i] + nums[j] == target){
int[] returnNums = {i,j};
return returnNums;
}
}
}
return null;
}
时间复杂度：O(n^2)，
空间复杂度：O(1),
这里稍微解释一下空间复杂度，百度的结果是这样的，
嗯，是对一个算法在运行过程中临时占用存储空间大小的度量。需要情调一下临时，它强调的是使用的辅助空间的大小，而不是全部的数据。以上面的例子为例，int[] nums是本身存储的数据，这个不算空间复杂度，最后的结果int[] returnNums才是临时占用的存储空间大小，这个算空间复杂度。
再回到原来的问题，官方给出了两种解决方案。
一、为了优化运行时间，我们需要一种更高效的方式来检查数组里面的差是否存在。如果存在，就需要查找它的下标。将数组的值与它的下标一 一对应的最好的方式无疑是哈希表。
使用哈希表，以空间换时间，我们可以将时间复杂度从O(n)减少到O(1)，它支持快速查找接近常量时间。为什么说接近呢？因为如果哈希表有碰撞发生，查找就会退化到O(n)时间。但是只要哈希函数选择恰当，在哈希表的查找时间就可以当做是O(1)时间。
一种简单的实现方式是使用两次迭代。在第一次迭代中，我们将数组的值和他的下标放到哈希表中，然后，在第二次迭代中，我们检查两者之差（target-nums[i]）是否存在于哈希表中。需要注意的是，这个差肯定不能使nums[i]本身！
public int[] twoSum2(int[] nums,int target){
Map<Integer,Integer> map = new HashMap<Integer,Integer>();
int i;
for(i = 0;i < nums.length;i++){
map.put(nums[i], i);
}
for(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)};
}
}
return null;
}
时间复杂度：O（n）。我们遍历了数组两次，既然哈希表的查询时间为O（1），因此时间复杂度为O（n）。
空间复杂度：O（n）。所需的额外空间大小取决于哈希表所容纳的元素数量，这接近于n个元素。
二、我们只需要遍历一次数组。当我们向后迭代的同时向哈希表插入数据，我们同时需要回头检查此时正确的差（target-nums[i]）是否已经存在于哈希表中，如果存在，我们就找到了答案然后立即返回。
public int[] twoSum3(int[] nums,int target){
Map<Integer,Integer> map = new HashMap<Integer,Integer>();
for(int i = 0;i < nums.length;i++){
int complement = target - nums[i];
if(map.containsKey(complement)){
return new int[]{map.get(complement),i};
}else{
map.put(nums[i], i);
}
}
return null;
}
时间复杂度：O（n）。我们仅仅遍历这个包含n个元素的数组一次。在哈希表中每次查找仅花费O（1）时间。
空间复杂度：O（n）。所需的额外空间大小取决于哈希表所容纳的元素数量，这接近于n个元素。