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.


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.


注意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就可以.


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;

Two Sum – Input is BST Tree


  1. 最优:dfs + set (integer): 遍历整个树,同时把已经遍历过的node的值放到一个set里,每遇到一个新的node看k – node.val是否存在于set中.适用于普通的binary tree.(注意这里可以用Set因为是dfs).
  2. 直接in-order traversal and serialize to an interger list, 然后two pointers find result.
  3. 同样dfs遍历整个树,对于当前的点,在树里search val == k – node.val的点. 注意这里一个corner case是: 找到的点不能为当前的点. 所以要对当前cur == node进行判断
    public boolean findTarget(TreeNode root, int k) {
        Set set = new HashSet<>();
        return helper(root, k, set);
    private boolean helper(TreeNode node, int k, Set set){
        if (node == null)
            return false;
        if (set.contains(node.val))
            return true;
        set.add(k - node.val);
        return helper(node.left, k, set) || helper(node.right, k, set);

    public boolean findTarget(TreeNode root, int k) {
        return dfs(root, root, k);
    private boolean dfs(TreeNode cur, TreeNode root, int k){
        if (cur == null)
            return false;
        return search(cur, root, k) || dfs(cur.left, root, k) || dfs(cur.right, root, k);
    private boolean search(TreeNode cur, TreeNode root, int k){
        if (root == null) return false;
        if (root.val + cur.val == k && root != cur)
            return true;
        return root.val > k - cur.val? search(cur, root.left, k) : search(cur, root.right, k);

Leave a Reply

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

You are commenting using your 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: