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.

BEST:

HashMap<Integer, Integer>: 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的话呢???


 

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: