2 Sum

出处 LeetCode 1

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

Solution

当处理当前节点需要依赖于之前的部分结果时,可以考虑使用哈希表记录之前的处理结果。其本质类似于动态编程(Dynamic Programming),利用哈希表以O(1)的时间复杂度利用之前的结果。

对于数组中的某个下标i,如何判断它是否属于符合条件的两个数字之一?最直观的方法是再次扫描数组,判断target – array[i]是否存在在数组中。这样做的时间复杂度是O(n2 ),效率不高的原因是没有保存之前的处理结果,每次都在做重复的工作。尽管效率不高,但是通过最直观的方法,我们发现处理当前节点需要依赖于之前的部分结果。如何保存之前的处理结果?可以使用哈希表。既然我们需要回答target – array[i]是否存在在数组中”,那不妨把值作为键,通过询问哈希表是否含有所需要的键来得到我们需要的回答。最终,根据题目,我们需要返回下标,那么把下标作为哈希表的值也是非常自然了。

Complexity

我们可以先对数组中的每个元素进行上述哈希处理,然后再从头至尾扫描数组,判断对应的另一个数是否存在在数组中,时间复杂度O(n + n)。事实上,我们可以利用动态编程的思想,仅仅利用已经处理的部分解:哈希表只存储前驱节点的信息。对于当前节点,判断前驱中是否含有对应值。当处理完当前节点,把当前节点加入哈希表,作为已经处理的部分解。这样,时间复杂度可以进一步减少为O(n)。

Code

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