两数之和

题目地址：https://leetcode-cn.com/problems/two-sum/

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

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

示例:

inform7
1
2
3
输入：nums = [2, 7, 11, 15], target = 9
输出：[0, 1]
因为 nums[0] + nums[1] = 2 + 7 = 9

暴力枚举

这里想必大家很快就能得到思路也就是双指针遍历所有两两相加判断是否与目标值相等

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

哈希表

但实际上按照上面我们去到数组当中找两个数相加为目标值的方式也就是在确定nums[i]的情况下与遍历找target - nums[i].既然是这样子那我们直接遍历一次记下所有的target-nums[i]再看数组当中存在taget-nums[i]不。若存在即返回下标为i与taget-nums[i]这个值的下标。那么我们就使用hash表去记录数组值为key下标为value

java
1
2
3
4
5
6
7
8
9
10
11
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];
}

总结

前者比起哈希表的解法未添加缓存信息因此需要花O(n^2)的时间复杂度来匹配,采用hash表记录增加了空间消耗时间复杂度O(n)因为配对的过程转为hash表查找。