算法——求两数之和

题目描述（来自LeetCode）：

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

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

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

思路：

由于前两天我刚学了动态规划，所以总想着先写个暴力递归出来，后来发现完全没必要。暴力解法就是两个for循环，第一个for循环选定第一个数，然后第二层for循环从num[j+1]开始依次和num[i]进行相加，结果等于target返回即可。

暴力解法：

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) {
                    return new int[]{i, j};
                }
            }
        }
        // 题目提示不可能没有结果，所以随便返回什么就行了
        return null;
    }
           

就这么简单，最终提交是62ms，反正没超时。

哈希表

我们可以借助哈希表，来对target - num[i]进行一个记录。key记录的是nums中的数字，value记录的是nums中对应数字的下标。

比如我现在就4个数字[3, 6, 8, 2]，target=11。

1. 首先把3存入哈希表–(3,0)
2. 然后计算target - 6 = 5，因为5在哈希表中没有对应的key，所以我们接着把6存入哈希表–(6, 1)
3. 然后计算target - 8 = 3，发现这个结果在哈希表中已经存在，至此我们就可以直接返回key=3的value值了。

public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> hashtable = new HashMap<>(nums.length - 1);
        hashtable.put(nums[0], 0);
        for (int i = 1; i < nums.length; i++) {
        	// 查询target - nums[i]的结果是否已经作为key存在于hashtable中了
            if (hashtable.containsKey(target - nums[i])) {
                return new int[]{hashtable.get(target - nums[i]), i};
            }
            hashtable.put(nums[i], i);
        }
        return null;
    }
           

该解法耗时2ms，时间节省许多。