【Leetcode】1.两数之和

1. 两数之和

题目

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

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

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

方法1（暴力法）

从头到尾遍历数组。对于每遍历到的一个元素num，在剩下的数组中查找是否存在target-num。如果存在则返回，否则继续遍历。

1
2
3
4
5
6
7
8
9
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 new int[0];
}

时间复杂度：O(n^2)
空间复杂度：O(1)

方法2（用哈希表，两次遍历数组）

我们解这道题的核心思路即：对于数组中一个给定元素num，查找数组中是否存在另一个元素target-num。

上一个方法之所以复杂度高，是由于在一个数组中查找一个元素需要O(n)的时间复杂度。如果查找这一步能优化，那么整个算法就可以优化。于是我们很容易想到能用O(1)的时间复杂度实现最快查找的数据结构：哈希表

算法步骤：

  1. 先遍历一次数组，将数组中所有元素加到哈希表中，key为元素的值，value为元素的索引
  2. 再从头到尾遍历数组。对于每遍历到的一个元素num，在哈希表中查找是否存在target-num。
1
2
3
4
5
6
7
8
9
10
public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for(int i = 0; i < nums.length; i++)
        map.put(nums[i], i);
    for(int i = 0 ; i < nums.length; i++){
        if(map.containsKey(target - nums[i]) && map.get(target - nums[i]) != i)
            return new int[]{i, map.get(target - nums[i])};
    }
    return new int[2];
}

时间复杂度：O(n)
空间复杂度：O(n)

方法3（用哈希表，一次遍历数组）

其实，我们只需遍历一遍数组就能把问题解决。从头到尾遍历数组。对于每遍历到的一个元素num，如果target-num在哈希表中，则返回。否则将当前元素加到哈希表中。

1
2
3
4
5
6
7
8
9
10
public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for(int i = 0; i < nums.length; i++){
        if(map.containsKey(target - nums[i]))
            return new int[]{map.get(target - nums[i]), i};
        else
            map.put(nums[i], i);
    }
    return new int[2];
}

时间复杂度：O(n)
空间复杂度：O(n)