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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

自己第一次尝试编写:

class Solution {

    public int[] twoSum(int[] nums, int target) {

        int[] arr;

        arr = new int[2]; 

        for(int i=0;i<nums.length;i++){

            for(int j=i+1;j<nums.length;j++){

                if(nums[j]+nums[i]==target){

                    arr[0]=i;

                    arr[1]=j;

                    return arr;

                }

            }

        }

        return null;

    }

}

遇到的问题:

1.for循环中"i"前面没加int定义以及应该用";",而不是","

2.数组的定义不会了,数组的长度是.length,而不是.length()

3.无解时缺少return null

4.由于是暴力破解,时间复杂度为,并不是最优解法

所以官方给出使用哈希表求解的方法,以空间复杂度来换取时间复杂度的降低

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; ++i) {
            if (hashtable.containsKey(target - nums[i])) {
                return new int[]{hashtable.get(target - nums[i]), i};
            }
            hashtable.put(nums[i], i);
        }
        return new int[0];
    }
}

其中containsKey()方法用于检查给定对象是否为键元素(key_ele)。

问题:我去查了containsKey()方法的源码,使用了迭代器,这个方法的时间复杂度应该是,不明白为什么把时间复杂度降下来了.

答:因为哈希表的存储性质

给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数。

而M是一个给定的值,因此降为了常数级别的时间复杂度.

也就是说,并非是改进了算法,而是改进了存储结构