LeetCode算法题，两数之和

题目出处：https://leetcode-cn.com/problems/two-sum/

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

解法1：暴力破解

static int[] iterMethod(int[] nums,int target){
    for (int i = 0; i < nums.length; i++) {
        for (int j = 0; j < nums.length; j++) {
            if ((i != j) && (nums[i] + nums[j] == target)){
                return new int[]{i,j};
            }
        }
    }
    return null;
}

第一种解决方式为暴力破解方式，就是写两重for循环，将所有组合都算一遍，最后得出结果时间复杂度为O(n^2)
时间复杂度计算方式：假设数组的长度为n，第一重循环需要n次，第二重循环则需要n*n次，所以是n^2

解法2：空间换时间，用HashMap

static int[] findByHashMap(int[] nums,int target){
    Map<Integer,Integer> numIndexMap = new HashMap<>(nums.length);
    for (int i = 0; i < nums.length; i++) {
        int sub = target - nums[i];
        if (numIndexMap.containsKey(sub)){
            return new  int[]{numIndexMap.get(sub),i};
        }
        numIndexMap.put(nums[i],i);
    }
    return null;
}

第二种方式，则是使用空间换取时间，建立一个hashMap，存放 数组 - 下标的形式。
循环获取每一个数组值的时候，用target减去当前数组值，然后通过HashMap的containsKey()方法判断map中是否有目标值，有就输出
这里只循环了一次所以时间复杂度为O(n)。
这里很多人有个疑问，因为其实containsKey的源码其实也是循环。为什么是O(n)呢？实际上，时间复杂度确实是O(n),因为hashMap的时间复杂度为O(1)（只有在hash冲突的时候，才会有O(n),这里的n并不是外部循环的n，而是HashMap内部每个Entry链表的长度），这就涉及到一个很经典的问题：为什么HashMap的时间复杂度为O(1)
经过测试当nums数组的长度够长时，用hashMap的方式是节省了很多时间的。这也符合解法1时间指数增长的结论。