题目一

给定一个整数数组 nums和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

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

关键点：

1.每种输入都会只会对应一个答案，说明只需要找到一个答案就可以停止

2.不能重复利用数组中同样的元素

解题思路：

一.常规思路，遍历中套遍历，时间复杂度为(o^2),空间复杂度为o(1);

public  class TwoSum {
public int[] toSum(int[] nums ,int num) throws Exception {
    for (int i = 0; i <nums.length ; i++) {
        for (int j = i+1 ;j <nums.length ; j++) {
          if(num ==nums[i]+nums[j]){
              return new int[]{i,j};
          }
        }
    }
  throw new Exception("没有匹配的值");
}

二，以上方法时间复杂度是（o^2）,数据量太大后，影响非常巨大，故需要考虑首先降低时间复杂度，考虑第一次遍历，放入hash表中，第二次遍历后直接中hash表中取值，不是嵌套遍历，故时间复杂度问o(n),空间复杂度为o（n）

  public int[] twoSum(int[] nums, int num) throws Exception {
    HashMap<Integer, Integer> hash = new HashMap<Integer, Integer>();
    for (int i = 0; i < nums.length; i++) {
        hash.put(nums[i], i);
    }
    for (int i = 0; i < nums.length; i++) {
        int a = num - nums[i];
        if (hash.containsKey(a) && hash.get(a) != i) {
            return new int[]{i, hash.get(a)};
        }
    }
    throw new Exception("没有匹配的值");

优化，放入hash表的同时，及开始匹配查找，如果以及查找出来，就不再进行hash表的添加，这样有一定几率，获得更好的结果