LeetCode 题解-1.two sum - 张磊的技术笔记

对Leetcode 1. two sum 题目的求解。

Problem Description#

Given an array of integers, return indices of the two numbers such that they add up to a specific target. You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example#

1
Given nums = [2, 7, 11, 15], target = 9,
2

3
Because nums[0] + nums[1] = 2 + 7 = 9,
4
return [0, 1].

Solution#

这道题题意很明确，即从一个数组中找出两个数，满足其和为target的要求，将这两个数的下标以数组的形式返回。首先，考虑brute-force穷举的方法，时间复杂度为 $\Theta(n^2)$ ，空间复杂度为 $\Theta(1)$ .

其次，考虑时间复杂度更低的方案。既然要找出两个数，我们不妨先确定一个数 $a$ ，如果数组中存在 $target-a$ ，那么我们就找到了答案。如果不行的话，我们再考虑其他数。至于如果确定数组包含某个数，我们考虑使用哈希表，来实现线性查询时间。在具体实现中，我们需要对数组进行两次遍历，第一次建立哈希表，第二次进行查询。需要注意，我们通过将数组元素的index作为value存入到hashmap中，以避免第二次遍历的时候出现自己加自己的情况。这种算法的时间复杂度为 $\Theta(n)$ ，空间复杂度为 $\Theta(n)$ .

Code#

1
class Solution {
2
    public static int[] twoSum(int[] nums, int target) {
3
        Map<Integer, Integer> m = new HashMap<Integer, Integer>();
4
        for (int i = 0; i < nums.length; ++i){
5
            m.put(nums[i], i);
6
        }
7
        for (int i = 0; i < nums.length; ++i){
8
           if (m.get(target - nums[i]) != null && m.get(target - nums[i]) != i){
9
               return new int [] {Math.min(i, m.get(target - nums[i])),
10
                                Math.max(i, m.get(target - nums[i]))};
11
           }
12
        }
13
        return new int [] {0,0};
14
    }
15
}

Improved Solution#

事实上，我们只需要一次遍历就可以解决问题。如代码所示，我们在遍历中首先确定查询当前元素的互补元素是否存在，如果存在的话，直接返回结果。然后在将当前元素加入哈希表，这样就可以避免将同一个元素考虑两次。

Improved Code#

1
class Solution {
2
    public static int[] twoSum(int[] nums, int target) {
3
        Map<Integer, Integer> m = new HashMap<Integer, Integer>();
4
        for (int i = 0; i < nums.length; ++i){
5
            if (m.containsKey(target - nums[i])){
6
               return new int [] {Math.min(i, m.get(target - nums[i])),
7
                                Math.max(i, m.get(target - nums[i]))};
8
            }
9
            m.put(nums[i], i);
10
        }
11
        return new int [] {0,0};
12
    }

Comments#

这个问题其实也可以转换成 Two Pointer 来求解，只不过需要先排序，找到两个元素之后还需要在原始数组中找到对应的下标。