图片 1

Design and implement a TwoSum class. It should support the following
operations: add and find.

/*
Date: March 21, 2016
170. Two Sum III - Data structure design
[My Submissions](https://leetcode.com/problems/two-sum-iii-data-structure-design/submissions/)Question

Total Accepted: **10075** Total Submissions: **41802** Difficulty: **Easy**

Design and implement a TwoSum class. It should support the following operations: add
 and find
.
add
 - Add the number to an internal data structure.find
 - Find if there exists any pair of numbers which sum is equal to the value.
For example,
add(1); add(3); add(5);find(4) -> truefind(7) -> false

Hide Company Tags
 [LinkedIn](https://leetcode.com/company/linkedin/)
Hide Tags
 [Hash Table](https://leetcode.com/tag/hash-table/) [Design](https://leetcode.com/tag/design/)
Hide Similar Problems
 [(E) Two Sum](https://leetcode.com/problems/two-sum/) [(E) Unique Word Abbreviation](https://leetcode.com/problems/unique-word-abbreviation/)
*/

import java.util.*;

public class TwoSumDataStructure {
    // add  O(1) time,    find(value) O(n) time,  space O(n)
    public static void main(String args[]) {
        TwoSumDataStructure twoSum = new TwoSumDataStructure();
        twoSum.add(1); twoSum.add(3); twoSum.add(5);
        System.out.printf(" find(4) = %b\n", twoSum.find(4));
        System.out.printf(" find(7) = %b\n", twoSum.find(7));
    }

    private static HashMap<Integer, Integer> map = new HashMap<>();

    public static void add(int input) {
        int count = map.containsKey(input) ? map.get(input) : 0;
        map.put(input, count + 1);
    }


    public static boolean find(int val) {
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            int num = entry.getKey();
            int y = val - num;
            if (y == num) {
                // For dumplicates, ensure there are at least  two individual numbers.
                if (entry.getValue() >= 2)  return true;
            } else if (map.containsKey(y)) {
                return true;
            }
        }
        return false;
    } 

}

https://www.lintcode.com/zh-cn/problem/two-sum-iii-data-structure-design/

Easy

My code:

add – Add the number to an internal data structure.
find – Find if there exists any pair of numbers which sum is equal to
the value.

import java.util.HashMap;
import java.util.Iterator;

public class TwoSum {
    private HashMap<Integer, Integer> map = new HashMap<>();

    /*
     * @param number: An integer
     * @return: nothing
     */
    public void add(int number) {
        // write your code here
        Integer integer = map.get(number);
        if (integer == null) {
            integer = 1;
        } else {
            integer++;
        }
        map.put(number, integer);
    }

    /*
     * @param value: An integer
     * @return: Find if there exists any pair of numbers which sum is equal to the value.
     */
    public boolean find(int value) {
        // write your code here
        Iterator<Integer> iterator = map.keySet().iterator();
        while (iterator.hasNext()) {
            Integer next = iterator.next();
            int res = value - next;
            if (res == next) {
                if (map.get(res) > 1) {
                    return true;
                }
            } else {
                if (map.containsKey(res)) {
                    return true;
                }
            }
        }
        return false;
    }
}

一道easy题一直TLE, tradeoff不会算?Take a look at the input data,
there’s a lot of “add” and a few “find”, so you should make “add” O(1)
definitely

public class TwoSum { HashMap<Integer, Integer> tracker = new HashMap<Integer, Integer>(); // Add the number to an internal data structure. public void add(int number) { if (tracker.containsKey { tracker.put(number, tracker.get + 1); } else { tracker.put(number, 1); } } // Find if there exists any pair of numbers which sum is equal to the value. public boolean find(int value) { for (Integer curr : tracker.keySet { int target = value - curr; if (tracker.containsKey { if (target != curr) return true; else { if (tracker.get >= 2) return true; } } } return false; }}// Your TwoSum object will be instantiated and called as such:// TwoSum twoSum = new TwoSum();// twoSum.add;// twoSum.find;

For example,
add(1); add(3); add(5);
find(4) -> true
find(7) -> false

class TwoSum {

    HashMap<Integer, Integer> hash;
    /** Initialize your data structure here. */
    public TwoSum() {
        hash = new HashMap<>(); 
    }
    /** Add the number to an internal data structure.. */
    public void add(int number) {
        if(hash.containsKey(number)){
            hash.put(number, hash.get(number) + 1);
        } else {
            hash.put(number, 1);
        }
    }
    /** Find if there exists any pair of numbers which sum is equal to the value. */
    public boolean find(int value) {
        for (Map.Entry<Integer,Integer> entry : hash.entrySet()){
            int i = entry.getKey();
            int j = value - i;
            if (i == j && entry.getValue() >= 2 || (i != j && hash.containsKey(j))){
                return true;
            }
        }
        return false;
    }
}

/**
 * Your TwoSum object will be instantiated and called as such:
 * TwoSum obj = new TwoSum();
 * obj.add(number);
 * boolean param_2 = obj.find(value);
 */

看的答案。不错。

思路:自己是用了一个map和一个set,add的时候效率较低,get的时候效率高,提交后是tle。因为case中add操作多,get操作少,如果get中进行遍历的话是可以通过的。

Anyway, Good luck, Richardo!

HashMap<Integer, Integer> map = new HashMap<>();
HashSet<Integer> set = new HashSet<>();

public FN_TwoSumIII() {

}

/** Add the number to an internal data structure.. */
public void add(int number) {
    if (map.containsKey(number)) {
        if (map.get(number) > 1) {
            return;
        } else {
            map.put(number, 2);
            set.add(number*2);
        }
    } else {
        for (Integer num : map.keySet()) {
            set.add(num + number);
        }
        map.put(number, 1);
    }
}

/** Find if there exists any pair of numbers which sum is equal to the value. */
public boolean find(int value) {
    return set.contains(value);
}

这道题目还是挺有意思的。虽然我这次没做出来。最后的AC解法和我的解法其实差不多。说下差距。

答案中还有一个方法很巧妙,每次get的时候判断判断target和当前遍历值的差值是否存在于map中。

  1. 我为了让逻辑更加清楚,用了更多的嵌套的if else,因此TLE,而AC
    的解法,就没有嵌套,更快。
  2. AC里面更好的解法是把unique的数字插在一个链表里面。重复出现的只用插入一次。这样做有两个好处。遍历链表的元素个数小于遍历哈希表的。其次,哈希表遍历的复杂度是
    O rather than O, k = number of key
private List<Integer> list = new ArrayList<Integer>();
private Map<Integer, Integer> map = new HashMap<Integer, Integer>();

// Add the number to an internal data structure.
public void add(int number) {
    if (map.containsKey(number)) map.put(number, map.get(number) + 1);
    else {
        map.put(number, 1);
        list.add(number);
    }
}

// Find if there exists any pair of numbers which sum is equal to the value.
public boolean find(int value) {
    for (int i = 0; i < list.size(); i++){
        int num1 = list.get(i), num2 = value - num1;
        if ((num1 == num2 && map.get(num1) > 1) || (num1 != num2 && map.containsKey(num2))) return true;
    }
    return false;
}

而链表的复杂度是O, m <= k

所以加入链表后作为一个遍历的机制,更快。

reference:

Anyway, Good luck, Richardo! — 09/02/2016

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图