题目：给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。

　　　你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。

示例：给定 nums = [2, 7, 11, 15], target = 9，因为 nums[0] + nums[1] = 2 + 7 = 9，所以返回 [0, 1]

解题思路：

　　　　1、普通思路-暴力法：遍历

　　　　　　从第一个元素开始，依次与后面的元素相加再与target判断，如全不满足继续从第二个元素开始往后遍历，直至有满足相等条件的元素为止。代码如下　　　

　　　　　　

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

• • 复杂度分析：时间复杂度：O(n^2).每一个数都尝试与其余数进行比较。空间复杂度：O(1)。无额外扩展空间，常数。

　　　　2、哈希表

　　　　　　为了对时间复杂度进行优化，需要使用更高效率的方法查询出数组中对于的结果。在查找元素时，如果找到目标元素则找到其索引取出，保持元素和索引相对应的方式就是使用哈希表。

　　　　　　初始代码如下：

1 public int[] twoSum(int[] nums, int target) { 2     Map
     
       map = new HashMap<>(); 3     for (int i = 0; i < nums.length; i++) { 4         map.put(nums[i], i); 5     } 6     for (int i = 0; i < nums.length; i++) { 7         int complement = target - nums[i]; 8         if (map.containsKey(complement) && map.get(complement) != i) { 9             return new int[] { i, map.get(complement) };10         }11     }12     throw new IllegalArgumentException("No two sum solution");13 }
     

 

　　　　　　首先遍历一遍数组，将数组元素及对应索引放入哈希表中。再进行第二遍遍历数组，检查哈希表中是否存在除其自身外满足条件的元素，存在则返回。从上述代码中可以看出哈希表其实是用空间去换取时间。

　　　　　　其时间复杂度只是对数组进行了遍历故为：O（n），空间复杂度存放了数组的n个元素故为：O(n).

　　　　　　再次分析上述代码，大家可以发现，对数组进行两次遍历似乎是不需要的，在进行比较元素的同时也可以进行哈希表的构建，满足条件时即可返回目标结果，优化后的代码如下：

1 public int[] twoSum(int[] nums, int target) { 2     Map
     
       map = new HashMap<>(); 3     for (int i = 0; i < nums.length; i++) { 4         int complement = target - nums[i]; 5         if (map.containsKey(complement)) { 6             return new int[] { map.get(complement), i }; 7         } 8         map.put(nums[i], i); 9     }10     throw new IllegalArgumentException("No two sum solution");11 }
     

　　　　　　在一次遍历中完成元素遍历比较及哈希表的构建，当然时间复杂度与空间复杂度并没有变化都还是O（n），但在实际的问题处理中效率会略有提升，因为目标结果未必一直在数组的尾部。