Two Sum

Leave a comment

November 20, 2016 by oneOokay

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.

Example:

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

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

UPDATE (2016/2/13):
The return format had been changed to zero-based indices. Please read the above updated description carefully.


这题要返回index,不能sort.

注意implementation是不是会有overflow. 用hashmap是不会overflow的. 因为如果是signed Integer的话, target – nums[i] 最大值就是Integer.MAX_VALUE,所以okay. (unsigned更加不会overflow)

如果要考虑overflow的话, 注意HashMap里面的key, 只能用Long而不是long. (因为hashmap的key是要有hashcode() function的class. hashmap的key的查找功能就是based on this. 就像int不能作为key,要用Integer一样. ) 把int转换long的时候还是用(long)value. 放了包含Long的Implementation,正常的不用Long,直接用Integer就可以.

BEST:

HashMap: O(N)

  • A + B = target => A = target – B.
  • 所以HashMap的value存index, key来用来查找. key可以放: A 或者 target – A.
    • 这里要想清楚key里面放什么,以及在用什么来判定map.containsKey(?)
    • key里面放nums[i]: 在for loop时,判断map.contains(target – nums[i])
    • key里面放target –  nums[i]: 在for loop时,判断map.contains(nums[i]).

Two pointers: 不行。因为要返回index,所以不能够sort。如果不返回index的话倒是可行,但是在于时间复杂度上还是会低于hashmap。因为Arrays.Sort()本身就是O(nlogn)的复杂度了。

Brutal: two for-loops O(N * N)


Two Sum II: given SORTED array:

Two pointers 最优. 首尾各一个pointer,如果sum==target,当前pointers的位置为解.如果sum>target,尾pointer –; 如果sum<target,首pointer ++.

HashMap是可以的. 和two sum I一样.

Binary Search: 可行. for loop,对于当前nums[i],在i+1到最后一个元素之间找到是否存在nums[x] == target – nums[i]的值.


Follow up: Two Sum III: 设计一个add和find的数据结构

Follow up:如果有多个解的话,求输出所有解的index的话呢???


    public int[] twoSum(int[] nums, int target) {
        int[] res = new int[2];
        if (nums == null || nums.length <= 1) return res;
        Map(Long, Integer) map = new HashMap();
        for (int i = 0; i < nums.length; i ++ ){
            if (map.containsKey((long)nums[i])){
                res[0] = map.get((long)nums[i]);
                res[1] = i;
                return res;
            }
            map.put((long)(target - nums[i]), i);
        }
        return res;
    }

 

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

%d bloggers like this: