Two Sum, Leetcode 解题笔记

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

第一反应当然是两层遍历,需要O(n^2)的时间复杂度,但是肯定有更好的解法。

首先考虑的是先排序,然后两个pointers分别从两头向中间找,这种方法时间复杂度是O(nlogn), 但是对于这道题并不适用,因为题目要求返回的是indices,一旦排序,indices会错乱,除非另外用array存储对应的变化,否则结果肯定不对。

除了这种办法,最好的方案就是利用HashMap,因为HashMap的查找复杂度是O(1), 先把numbers存入HashMap,再遍历查找是否存在A1 = target – A2,此方法仅需要O(n)的时间复杂度。注意,一个容易出错的地方是必须判断A1和A2的index不相同。代码如下:

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int[] ret = new int[2];
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int i = 0; i < numbers.length; i++){
            map.put(numbers[i], i);
        }
        for(int i = 0; i < numbers.length; i++){
            if(map.containsKey(target - numbers[i]) && i != map.get(target - numbers[i])){
                ret[0] = Math.min(i+1, map.get(target - numbers[i]) + 1);
                ret[1] = Math.max(i+1, map.get(target - numbers[i]) + 1);
                break;
            }
        }
        return ret;
    }
}

总结,学会利用HashMap,遇到类似问题首先考虑HashMap的可行性,因为它的查找复杂度最低。

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s